Time Complexity

How to describe runtime of an algorithm?

There are 3 notations used to describe time complexity.

It describes an upper bound on time.

It is asymptotic lower bound concept.

It is the tight bound on a runtime, an algorithm is theta(n) if it is O(n) and omega(n).

As Big O is the upper bound on an algorithm and it is the maximum amount of time required.

Following are the terminologies used to calculate time complexity

Ignore the constants

We drop the constants in runtime. An algorithm that is having O(2N) is same as O(N).
Ex : O(2N) is treated as O(N).
Drop the non-Dominant terms

We should drop the non-Dominant terms as they are negligible for large input size and take the largest term into consideration.
Ex : O(N + log N) will become O(N) O(N^3 + N^2) will become O(N^3)
Log N runtime

When the number of elements in the problem space gets halved each time, that will likely be O(log N) Base of log does not matter for Big O notation.
Ex : For binary search tree, Time complexity for finding an element is O(log N).
Recursive runtime
```
 int fib(int n) {
     if (n <= 1) return n; // Base case
     return fib(n - 1) + fib(n - 2);
 }
```
We write the recurrence relation and calculate the time in terms of input size.
Identify the Base case and recursive case.

Time complexity for the above algorithm is exponential O(2^N)

Calculating the time complexity seems difficult at first, but once you understand the concepts it is fairly easy.

Comments