Time Complexity

Table of Contents

Given a piece of code, how to determine the complexities without much effort? Each piece of code has a time complexity associated with it which you need to learn. Next time, you see any complex code break it into individual pieces and count the time complexity.

Statements

Each of the statement in an algorithm takes a constant time to execute. If the algorithm procedure has N statements.

Then,

statement 1;

statement 2;

statement 3;

statement n

\begin{aligned} &Constant \hspace{1mm}time = \mathcal{O}(1)\\ \\ &Total\hspace{1mm} running \hspace{1mm}time = \mathcal{O}(1) + \mathcal{O}(1) + \dots+ \mathcal{O}(1)\\ \\ \end{aligned}

Sum of all the constant times is also a constant.

Therefore,

The Total running time is also constant $\mathcal{O}(1)$ .

If-Then-Else

For the if-then-else block, only one block gets executed, based on the condition. But the run time for the block may be different from other blocks in the if-then-else statement.

if (condition) then
{

    block 1;

}
else
{

    block2;

}

Therefore,

\begin{aligned} Total \hspace{1mm}runtime = Max(time(block 1), time(block2)); \end{aligned}

For Example,

Total\hspace{1mm} runtime = Max(\mathcal{O}(1), \mathcal{O}(n))

Depending on the condition the total runtime of if-then-else block could be

Loops

The loop runs for N time for any given N value. The statements inside the loop also get repeated for N times.

for j = 1 to N do {

    statements;

}

The loop runs for N time and each of the statements inside the loop takes $\mathcal{O}(1)$ . Then the total runtime is given below.

\begin{aligned} &Total \hspace{1mm}runtime = N * \mathcal{O}(1)\\ &= \mathcal{O}(N) \end{aligned}

Nested Loop

The nested loop is not different than the single loop statement. Now that there are two loops their running time get multiplied.

for i = 1 to N do
{

    for j = 1 to M do    
    {

        Statements;

    }
}

Suppose the outer loop runs $N$ times and an inner loop has a complexity of $\mathcal{O}(M)$ .

Total \hspace{1mm}Time\hspace{1mm} Complexity = \mathcal{O}(N * M)

Let us say that the inner also runs for N times, the total complexity is given by

= \mathcal{O}(N^2)

Functions

Functions are blocks themselves and contain many other statements. The total time of a function depends on these statements.

Suppose a function $f(N)$ takes $\mathcal{O}(1)$ and there is another function $g(N)$ that has a loop. Then,

Total \hspace{1mm}Time\hspace{1mm} Complexity \hspace{1mm}of \hspace{1mm}g(N) = \mathcal{O}(N)

because of the loop.

Statements with Function

A loop statement can be inside of a function, but it is also possible that a function is inside of a loop.

for j=1 to N do {

    g(N);

}

Since, we already know that the running time of the function $g(N)$ is $\mathcal{O}(N)$ .

\begin{aligned} &Total \hspace{1mm} Complexity = N * \mathcal{O}(N)\\ &= \mathcal{O}(N^2) \end{aligned}

This is because the loop runs for N time and repeats the function N times as well.