Suppose we want to add a large number of integers, how long will this operation take? The first question that comes to mind is the number of integers, let’s assume this number is n. Can we specify exactly how long this will take? Yes, we can for a specific computer. It can never be said universally because the computation power largely depends on the computer’s processor and memory (here, primary memory is referred to). Naturally, a Celeron processor will have much less processing power compared to a Core i-7.

Moreover, it is not logical to count how many statements are there in a program or how many statements are executed. Because the number of statements needed to solve a problem depends on the programming language. It is seen that a program in C might require 100 statements, but the same program in Python might be done in just 10 lines.

For solving this problem, the complexity of the algorithm is expressed in asymptotic notation. Based on the input size, the type of complexity that will arise at runtime is determined through asymptotic notation. Typically, we can measure the complexity of an algorithm through three types of notations –

## Big-O

Big-O is a measure of the maximum time it takes to run an algorithm (worst case), that is, the algorithm’s upper bound (upper bound) is expressed through this notation.

*f*(*n*) = O(*g*(*n*)) (read as “*f* of *n* is big oh of *g* of *n*”) iff (if and only if) there exist positive constants *c* and *n*0 such that *f*(*n*)≤*cg*(*n*) for all *n*,

example, 3*n*+2=O(*n*) as 3*n*+2≤4*n* for all *n*≥2

as for all *n*≥5

*g*(*n*) is upperbound on the value of *f*(*n*) for all *n*, *n*≥*n*0

Theory:

If then

## Big-Ω

Big-Ω is a measure of the minimum time required to run an algorithm (best case), that is, the algorithm’s lower bound (lower bound) is expressed through this notation.

*f*(*n*) = Ω(*g*(*n*)) (read as “*f* of *n* is omega of *g* of *n*”) iff there exist positive constants *c* and *n*0 such that *f*(*n*)≥*cg*(*n*) for all *n*, *n*≥*n*0

example, 3*n*+2=Ω(*n*) as 3*n*+2≥3*n* for all *n*≥1

as for all *n*≥1

*g*(*n*) is only a lower bound on *f*(*n*)

Theory:

If then

## Big-Θ

Big-Θ is the average calculation of the maximum or minimum time an algorithm will take to run.

*f*(*n*) = Θ(*g*(*n*)) (read as “*f* of *n* is theta of *g* of *n*”) iff there exist positive constants *c*1, *c*2, and *n*0 such that *c*1*g*(*n*)≤*f*(*n*)≤*c*2*g*(*n*) for all *n*, *n*≥*n*0

example, 3*n*+2=Θ(*n*) as 3*n*+2≥3*n* for all *n*≥2 and 3*n*+2≤4*n* for all *n*≥2, so

*c*1=3, *c*2=4, and *n*0=2

*g*(*n*) is both an upper and lower bound on *f*(*n*)

Theory:

If then

The figure above depicts a comparison of these three types of notation.