How to calculate Time Complexity for a given algorithm

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.