top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration

Facebook Login
Site Registration

Can anyone suggest how you can measure space and time complexities for any algorithms in C/C++?

+1 vote
56 views

Can anyone suggest how you can measure space and time complexities for any algorithms in C/C++?

posted Dec 25, 2016 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

Time Complexity
Just count the number of steps of the program with the input size n. Lets understand by the example

bubble_sort(int a[])
{
  int n=length(a);
  int temp; 
  for (i=0; i< n; i++) 
      for (j=0; i<n; j++)
      {
         if (a[i] > a[j])
          { 
              temp = a[I];
              a[i] = a[j];
              a[j] = temp;
           }
       }
}

Because of the for statement at line 3, the block between lines 4 and 12 gets run exactly N times, where N is the length of the list. This block is itself a for loop that runs exactly n times, so the if block between lines 6 and 10 gets executed N^2 times in all.

So
Line 1-2: Executed once
Line 3: Executed once (sets i = 1 at the beginning)
Line 4: Executed n times (sets J = 1 once per value of I)
Line 5: Executed n^2 times
Line 6: Executed n^2 times
Line 7: Executed between 0 and n^2 times.
Line 8: Executed between 0 and n^2 times.
Line 9: Executed between 0 and n^2 times.
Line 10: Executed n^2 times (increments j and jumps to line 5)
Line 11: Executed n times (increments i and jumps to line 4)

So if we count the number of times a line gets executed, we have something between 6N^2+2N+3 (worst case), and 2N^2+2N+3 (best case). Which tells us that as the N increases then the time of the execution is proportional to N^2 which means time complexity of the program is O(n^2).

Space Complexity
The space complexity of an algorithm is measured as the maximum amount of space used at any one time. In this case we need array a which is of the order n and one temp variable for the swap. So the space complexity of the above program is n+1 or ~n.

answer Dec 25, 2016 by Pushpak Chauhan
Similar Questions
+1 vote

What are the time complexities of some famous algorithms like below:

Binary Search :
Merge Sort:
Insertion Sort:
Quick Sort:
Selective Sort:
Finding max & min for a given set of number:

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...