Algorithm Time Complexity

Advertisements
Advertisements

 38 total views

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.

Before you begin, learn the basics of algorithm performance and its complexity.

An algorithm has following types of code and we are going to learn time complexity for each one of them.

  1. Statements
  2. If-Then-else
  3. Loops
  4. Nested loops
  5. Functions
  6. Statements with functions.

Statements

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

Advertisements

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

\mathcal{O}(1) \hspace{1mm}or\hspace{1mm} \mathcal{O}(n)

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.

Advertisements
\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.

Bestseller

Introduction to Algorithms, 3rd Edition (The MIT Press) 3rd Edition

Best book for students with little programming experience. The algorithms are designed and explained in easy to understand manner. The book includes many exercises and problems. The text is intended primarily for students studying algorithms or data structures. As it discusses engineering issues in algorithm design, as well as mathematical aspects, it is equally well suited for self-study by technical professionals.

Advertisements
Advertisements
Advertisements