How to calculate the time complexity and space complexity

[lindsayy]

Hi, may i know how to calculate the time complexity and space complexity of this code

 
#include<iostream>
using namespace std;

 struct Run{ 
    int first; 
    int last; 
    int pos; };  

int main()
{
   int Array[] = {1,2,3,4,0,5,6,7};
   int size = sizeof Array / sizeof Array[0];
   cout << "Unsorted array: ";
   for ( int i = 0; i < size; i++ )
   {
       cout << Array[i] << " ";
   }
   cout << "\n\n";
   

   int nruns = 1;
   for ( int i = 1; i < size; i++ ) 
   {
       if ( Array[i] < Array[i-1] ) {
           nruns++;
       }
   }
  
   Run* runs = new Run[nruns];
   int nr = 0;                            
   runs[nr] = Run{ 0, 0, 0 };             
   for ( int i = 1; i < size; i++ )
   {
      if ( Array[i] < Array[i-1] )          
      {
         runs[nr].last = i - 1;
         runs[++nr] = Run{ i, i, i };
      }
     
   }
   runs[nruns-1].last = size - 1;
      
   cout << "Runs are (first:last)\n";
   for ( int j = 0; j < nruns; j++ ) 
   {
       cout << runs[j].first << " : " << runs[j].last << '\n';
   }
    
    
   
   int* newarray = new int[size];
   for ( int i = 0; i < size; i++ )
   {
      nr = -1;
      for ( int j = 0; j < nruns; j++ )
        {
         if ( runs[j].pos <= runs[j].last && ( nr == -1 || Array[runs[j].pos] < Array[runs[nr].pos] ) ) 
         {
           nr = j;  
         }
        }
       
      newarray[i] = Array[runs[nr].pos];
      runs[nr].pos++;
   }
  
   cout << "\nSorted array: ";
   for ( int i = 0; i < size; i++ )
   {
       cout << newarray[i] << " ";
   }
    
}

[jonnin]

space is adding up the variables by size in bytes. sizeof(run)*nruns + size*2*sizeof(int) + 8*sizeof(int) (line 12) gets you close. Typically you only care about the variable sized entities, the size and nruns memory allocations.

time is N*N .. remember its not exact, and your biggest loop is line 52 (by number of iterations).
I mean more precisely (but not big-O approach) its size*nruns + size*5 ... the for loops' iteration counts. Big-O only keeps the dominate term.

[lindsayy]

i see, so the time complexity is O(N^2) right?

[jonnin]

yes, N*N and N^2 are the same thing :)

remember this stuff can get weird.
what are you counting? conditions that bypass the work sometimes affect big-O. For example shell-sort LOOKS like N*N if you do the drive-by 'well, its got 2 nested for loops' approach to analysis. You do that too: if you want to count the assignments, that if condition that blocks them makes it a bit more hairy than just N*N. But if you assume that the if statement does MORE WORK (it does) than the assignment itself, and you want to know how long the thing will run, and the if executes every time (it does) ... then N*N works.