Finding out time complexity of your code helps you to develop better programs that run faster. Some programs are easy to analyze, but when we have loops, nested functions or recursion; the situation gets tricky.

The time complexity can be determined by analyzing the program's statements going line by line. The most common metric used to analyze time complexity is Big O Notation.

Big O notation cares about the worst case scenario. For ex: in linear search of an array of N elements, searching for the last element is the worst case scenario which will take O(N) time.
Big O = Big Order Function(Drop the lower order and constant terms). For ex: O(7n³-n²+5) = O(n³).

If we plot the most common Big O Notations, we would get the graph:

Let’s take a look, how to translate code into time complexity.

If we have n statements performing basic operations such as assignment, reading a variable or comparision then we can assume the time complexity for each statement is O(1).

T(n) = t(statement1) + t(statement2) + ... + t(statementN).

If each statement executes a basic operation then we can say it takes constant time i.e. O(1), be it 1 or 100 lines of statements(executing basic operation).

Cosider a C++ program to multiply two integers.
int a=10;
int b=5;
int mul=a*b;
cout<< "Product: " << mul;
These statements are basic operations and each of them will take O(1) time. So summing up, the time complexity will still remain O(1) and not 4*O(1).

if (condition) {
statement1;
statement2;
} else {
statement3;
}

The time complexity of this would be:
T(n) = MAX of ([t(statement1) + t(statement2)], [t(statement3)])

For ex: Suppose statement1 takes O(nlogn), statement2 takes O(n) and the condition is happened to be true then time complexity would be O(max of [nlogn,n]) = O(nlogn).

Constant time loops:

If the loop bounds a constant number then the time complexity would also be constant time i.e. O(1).

for (int i = 0; i < 10; i++) {
cout << i;
}
That code is O(1) because it no longer depends on the input size. It will always run the statement ten times.

Linear time loops:

For any loop, we find out the runtime of the block inside them and multiply it by the number of times the program will repeat the loop.

for (int i = 0; i < N; i++) {
statement1;
statement2;
}

For this, the loop will execute the block N(input) times and thus we get the time complexity:

T(n) = n * [ t(statement1) + t(statement2) ]

Logarithmic time loops

An algorithm is O(logn) if it takes a constant time to cut the problem size by a fraction.

Consider the following loop where the iterator is doubled after every loop.
for(int i = 1; i <= N; i *= 2 ) {
cout << i;
}

If we observe carefully, the value of i is doubling every time. Initially i = 1, and in subsequent steps i = 2,4,8 and so on. Let us assume that the loop is executing some k times. At kth step 2^k = n, and at (k + 1)th step we come out of the loop. Taking logarithm on both sides, gives

log(2^k) = log(n)
klog2 = logn
k = logn
//Assume the base=2

Nested Loops

Sometimes you will have problems related to 2D arrays then you will have to use 2 loops to visit all the array elements.
for (let i = 0; i < n; i++) {
statement1;
for (let j = 0; j < m; j++) {
statement2;
}
}

Then the time complexity would be O(n*m). If you had n instead of m then it would have been O(n²).

T(n) = n * [t(statement1) + m * t(statement2)]

Function Calls

for (let i = 0; i < n; i++) {
function1();
for (let j = 0; j < n; j++) {
function2();
for (let k = 0; k < n; k++) {
function3();
}
}
}


Depending on the runtime of each function, we will get different time complexities.
If they are all constants, O(1) then final runtime would be O(n³).
Suppose function1, function2 are constant and function3 has O(n²) runtime then this program will have an overall runtime of O(n⁵).

In general,
T(n) = n * [ t(fn1()) + n * [ t(fn2()) + n * [ t(fn3()) ] ] ]

Analyzing the runtime of recursive functions might get a little tricky. There are different ways to do it. One intuitive way is to explore the recursion tree.

function fn(n) {
if (n < 0) return 0;
if (n < 2) return n;
return fn(n - 1) + fn(n - 2);
}

Let's see how many calls will be made:

• If n=2, then you will have 3 calls i.e fn(2) which calls fn(1) & fn(0).
• If n=3, then you will have 5 calls ie. fn(3) which calls fn(2)(which again calls fn(1) and fn(0)) and fn(1).

The total no. of calls atmost can be 2ⁿ in worst case. So the time complexity would be O(2ⁿ) in this example.