How to calculate Time Complexity for a given algorithm

One of my friends wanted to know "How to calculate the time complexity of a given algorithm". My obvious answer to him was... "Why do YOU want to calculate it?. There are tools available that do it for you!!" (E.g. Analyze menu in VS Team Suite, NDepend are a few). Well... I don't want to say what his answer was, but he wanted to know :-)

In my personal view, it's a good to know "cool" thing, but not really required for ALL.

With that note, let me write a small program and calculate the time complexity for it.

Here is a sample code to remove an invalid character from an array.

    1: namespace TimeComplexity
    2: {
    3:     class Program
    4:     {
    5:         static void Main(string[] args)
    6:         {
    7:             char[] arr = { 'a', 'b', 'b', 'd', 'e' };
    8:             char invalidChar = 'b';
    9:             int ptr = 0, N = arr.Length;
   10:             for (int i = 0; i < n; i++)
   11:             {
   12:                 if (arr[i] != invalidChar)
   13:                 {
   14:                     arr[ptr] = arr[i];
   15:                     ptr++;
   16:                 }
   17:             }
   18:  
   19:             for (int i = 0; i < ptr; i++)
   20:             {
   21:                 Console.Write(arr[i]);
   22:                 Console.Write(' ');
   23:             }
   24:             Console.ReadLine();
   25:         }
   26:     }
   27: }

Output for the above code will look like

 a d e

Let's look at each loop one at a time. That's the key; you calculate the time complexity for each loop

    1: for (int i = 0; i < N; i++)
    2: {
    3:     if (arr[i] != invalidChar)
    4:     {
    5:         arr[ptr] = arr[i];
    6:         ptr++;
    7:     }
    8: }

The above Code snippet contains a lot of basic operations which will be repeated. (That's why it's called a loop.. duh !!). The basic operations it contains are

 

int i=0;	This will be executed only once. The time is actually calculated to i=0 and not the declaration.
i<N;	This will be executed N+1 times
i++ ;	This will be executed N times
if(arr[i]!=invalidChar)	This will be executed N times
arr[ptr]=arr[i];	This will be executed N times (in worst case scenario)
ptr++;	This will be executed N times (in worst case scenario)

 

Note: I considered the worst case scenario and am calculating the Worst Case Time Complexity for the above code

So the number of operations required by this loop are

 

{1+(N+1)+N}+N+N+N = 5N+2

 

The part inside the curly braces is the time consumed by Loop alone (i.e.. for(int i =0;i<N;i++)), it is 2N+2. Keep this mind; it is usually the same (unless you have a non-default FOR loop)

 

Now for the second loop

    1: for (int i = 0; i < ptr; i++)
    2: {
    3:     Console.Write(arr[i]);
    4:     Console.Write(' ');
    5: }

 

Remember, a loop takes 2N+2 iterations. So, here it will take 2ptr+2 operations. Again, considering the worst case scenario ptr will be N so the above expression evaluates to (again) 2N+2. Then there are these additional 2 operations of Console.Write with will be executed N times each (Again, worst case scenario).

So the above code snippet will take

{1+(N+1)+N}+N+N = 4N+2

 

Oh.. I almost forgot the other statements

 

char[] arr = { 'a', 'b', 'b', 'd', 'e' };	This will be executed N times
char invalidChar = 'b';	This will be executed 1 time
int ptr = 0;	This will be executed 1 time
N = arr.Length;	This will be executed 1 time
Console.ReadLine();	This will be executed 1 time

 

Note: The character array initialization will actually execute N times. This is because you are assigning one character at a time.

So the rest of the code requires

N+4

Adding everything up I get

(N+4)+(5N+2)+(4N+2) = 10N+8

So the asymptotic time complexity for the above code is O(N), which means that the above algorithm is a liner time complexity algorithm.

There you have it, now you know how to calculate the time complexity of a simple program.