question on time complexity

here is a very fundamental question.... many a times i have seen if anybody wants to talk about performance of a code then they refer time complexity . what exactly does it mean ?

my confusions are

(1) is it the time to complete the execution of code ? ( i guess it is not. though not sure)

(2) suppose a code has time complexity O(n*log n ) . what does it mean ? what does n stands for ?

i found n has different meaning in different context .
(a) n may be number of data . (right ?)

( b) n may be number of iteration .

(c) n may be time ? (right?)



i am really confused what exactly n stand for ? is not it a unique thing?



(3) At last , i want to know how can i calculate the time complexity of a code ? yes, there are examples in the book (e.g selection sort,merge sort,...many many) , i am not talking about those things.

i am saying ....suppose i wrote an arbitrary code which works. how do i start calculating its complexity ? can u give some tips or in general steps ?




if anybody give responses according to question i will be highly benefited....bcoz those are my confusions.

thanks for reading this stuff.

> (1) is it the time to complete the execution of code ?
Only indirectly. It is used to compare algorithms completely independent of any implementation bias.
Theoretically at least, if you have two algorithms which are O(nlogn) and O(n*n), the first is better since the result grows more slowly. Which means its quicker to do the same amount of work.

For a given algorithm, say quicksort which is O(nlogn), and a given machine, OS, compiler, you can work out the value of some constant 'C', such that
time = C * n * log(n)
Having timed how long it takes to sort say n=1000 integers (to determine the value of C), you can use that to predict with some reasonable accuracy how long it would take to sort say 5000 integers.

One more thing to note - the value of n has to be pretty large to get a true idea of the relationship between the complexity and the amount of real time it takes to execute.
Try comparing quicksort and bubblesort for small values of n to see what I mean.

> (2) suppose a code has time complexity O(n*log n ) . what does it mean ? what does n stands for ?
The size of the data - n is how many elements you have in your array for example.

> (3) At last , i want to know how can i calculate the time complexity of a code ?
It pretty much boils down to examining the nature of the loops in the algorithm, like how they're nested one inside another.

Code:

---

for ( i = 0 ; i < n ; i++ )
This is O(n)

for ( i = 0 ; i < n ; i++ ) for ( j = 0 ; j < n ; j++ )
This is O(n*n)

for ( i = 0 ; i < n ; i++ ) for ( j = 0 ; j < n ; j++ )
for ( k = 0 ; k < n ; k++ )
Although its tempting to write O(n*n+n) or O((n+1)*n), multiple terms and constants are
not usually shown.  For very large n, its only the major term which is going to be significant.
So this is also O(n*n)

---

From a pragmatic point of view, you run your code with lots of values of n, and attempt to plot a graph of n vs. time.

f(n) = O(g(n)) iff f(n) <= c * g(n)

where c is a constant and for all n >= some initial n.

hi salem....you are saying n is the number of data elements.

but in this code,

for ( i = 0 ; i < n ; i++ )
This is O(n)

n may be a simply loop invalidation index instead of



another question, suppose i have time complexity O(n * n) ... and number of elements is 2 ....

so it means O(2 *2) = O(4) // can i do it? does it make sense ?


one more question

for ( i = 0 ; i < n ; i++ ) for ( j = 0 ; j < n ; j++ )
for ( k = 0 ; k < n ; k++ )

it should be complexity O(n^3).....bcoz applying unitary method like below...

for i=0,j=0......k loops n times

for i=0,j loops n times

so ultimately combining these i should get complexity O(n*n*n) = O(n^3)


i may be severly wrong......can u tell why it cant be done ?


>>>From a pragmatic point of view, you run your code with lots of values of n, and attempt to plot a graph of n vs. time.

great !! its a good idea ....so i can verify time complexity without calculating for any arbitrary code.

for example if the code has time complexity O(n) graph shold be linear , if the code has O(n^2) then graph should be parabola .......hmmm .

but imporatant thing is what would the x co-ordinate ? you are saying time ...... do i need to use time function from the library ? or simply the iteration number

can you give a small example code so that i can copy / paste the data file and plot in in the GNU plot software ti convince myself.

>n may be a simply loop invalidation index instead of
Instead of what? It iterates from 0 to n, so the loop without any other context is still linear.

>it should be complexity O(n^3)
No, it shouldn't. The j loop is nested within the i loop, but the k loop is not nested in either. A better formatted example would be

Code:

---

for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) {
    [...]
  }
}
for (k = 0; k < n; k++) {
  [...]
}

---

Because the quadratic time of the i and j loops dominate, the linear time of the k loop is ignored. Thus the algorithm is O(n * n). If the k loop were nested within the j loop then the complexity would be cubic as you thought.

>> another question, suppose i have time complexity O(n * n) ... and number of elements is 2 .... so it means O(2 *2) = O(4) // can i do it? does it make sense ?

No. "Big-O" looks at the behavior of functions as the inputs grow indefinitely. It does not make sense to look at the complexity of a function with a given input, it will always be O(1), that is, will always take the same amount of time.

To actually time it, for simple algorithms, go ahead and count the number of iterations. As the algorithms grow in complexity (not computational complexity, just more being tested/done), then use a timer as it will likely not be clear where to count what.

thanks for clearing my doubts.

but i dont follow how do i plot the complexity of the graph...

>>From a pragmatic point of view, you run your code with lots of values of n, and attempt to plot a graph of n vs. time

>>To actually time it, for simple algorithms, go ahead and count the number of iterations. As the algorithms grow in complexity (not computational complexity, just more being tested/done), then use a timer as it will likely not be clear where to count what.


i dont follow how do i do it . what vs what ?

lets take kip's formatted code.

Code:

---

for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) {
    [...]
  }
}
for (k = 0; k < n; k++) {
  [...]
}

---

so i need a data file to plot . right ? so what is X and what is Y in this case for plotting ?

something i should store in the data file like....

fprintf(fp,"%d,"%d", X,Y) // what would be X and Y here for the Kip's code?


graph should be a parabola bcoz of dominating O(n*n) . can anybody help me to show me what i should write in that code to get the data file ? i want an example....you people are telling to use time function ...but which way :confused:


N.B ...it would be good if anybody have/know some good links on time complexity for further reading.

thanks

Thanks to Kip Neuhart for fixing the nesting of my ambiguous loops :)

> but imporatant thing is what would the x co-ordinate ?
x is the value of n, say 10,20,50,100,200,500,1000,......
y is time, how long it took to deal with a sample size of your chosen 'n'

>x is the value of n, say 10,20,50,100,200,500,1000,......
>y is time, how long it took to deal with a sample size of your chosen 'n'

here i tried this way...but failed.

Code:

---

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int main()
{
 
FILE * fp1 = fopen("c:\\files1","w");
int j ;

for(int i =0 ;i<10000;i=i+10)

for( j =0;j<10000;j=j+10)
{
  int t1  = time(NULL)%1001;
 
  fprintf(fp1,"%d",i+j);  // chosen sample i and j ;

  int t2 = time(NULL)%1001; //just scaling
 
  fprintf(fp1,"  %d",t1-t2);  //  time taken to write in the file.
 
  fprintf(fp1,"\n");

}

}

---

my data file is "files1".......but it is not giving parabola. where is the mistake ?

can anybody tell why it is not working ? how can i get the time complexity graph ?

int t1 = time(NULL)%1001;

fprintf(fp1,"%d",i+j); // chosen sample i and j ;

int t2 = time(NULL)%1001; //just scaling

This isn't any work based on the value of n

Code:

---

int sizes[] = { 10,20,50,100,200,500,1000 };
for ( i = 0 ; i < 7 ; i++ ) {
  t1 = time();
  for ( j = 0 ; j < sizes[i] ; j++ ) {
    // do some work
  }
  t2 = time();
  printf( "size %d took %d\n", sizes[i], t2-t1 );
}

---

Then you could plot sample size vs. time