TIME COMPLEXITY

The time complexity of an algorithm is the total amount of time required by an algorithm to complete

its execution. The time taken by any piece of code to run is known as the time complexity of that code.

The lesser the time complexity, the faster the execution.

In analysis algorithm, Big Oh is often used to describe the worst-case of an algorithm by taking the

highest order of a polynomial function and ignoring all the constants value since they aren’t too

influential for sufficiently large input. So, if an algorithm has

running time like f(n) = 3n + 100, we can simply state that algorithm has the complexity O(n) which

means it always execute at most n procedures(ignoring the constant ‘100' in between and also the

constant ‘3' being multiplied by n). Thus, we can guarantee that algorithm would not be bad than the

worst-case.

Big Omega is often used to describe the best-case running time of an algorithm by choosing the

lowest order of the polynomial function and ignoring all the constants.

Example: prove that f(n) = 5n² + 3n has Big Ω(n)

We know that the lowest order of the polynomial function f(n) (i.e. 1) is less than n²,

thus we can conclude that f(n) has a big Ω(n)

Big Theta describes the running time of an algorithm which is both best case and worst case.

This idea might be a big tricky to grasp at first but don’t worry, it’s not that different from Big Oh or

Big Omega, though if you don’t completely get the concept of Big Oh and Big Omega, you might

want to go through that again before moving onto this. An algorithm has both best and worst case

running times. What does that mean? It means that the algorithm is both Big Oh and Big Omega at

the same time. In simpler words, if we consider a polynomial function f(n) = 3n³ + 4n, the Big Theta

of the function is going to neither be greater nor smaller than the highest order of the function.

It’s going to be exactly equal to it, which in this case is going to be n³.

Example: prove that f(n) = 3n has Big Θ(n)

Since the highest and the lowest order of the polynomial is 1, the big Θ of f(n) is going to be n.

SCIENTAX