question on time complexity

This is a discussion on question on time complexity within the C++ Programming forums, part of the General Programming Boards category; here is a very fundamental question.... many a times i have seen if anybody wants to talk about performance of ...

  1. #1
    Registered User
    Join Date
    Dec 2003
    Posts
    92

    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.
    blue_gene

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,548
    > (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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    f(n) = O(g(n)) iff f(n) <= c * g(n)

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

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  4. #4
    Registered User
    Join Date
    Dec 2003
    Posts
    92
    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.
    blue_gene

  5. #5
    Registered User
    Join Date
    May 2004
    Posts
    127
    >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.

  6. #6
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    >> 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.

  7. #7
    Registered User
    Join Date
    Dec 2003
    Posts
    92
    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


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

    thanks
    blue_gene

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,548
    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'
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Registered User
    Join Date
    Dec 2003
    Posts
    92
    >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 ?
    blue_gene

  10. #10
    Registered User
    Join Date
    Dec 2003
    Posts
    92
    can anybody tell why it is not working ? how can i get the time complexity graph ?
    blue_gene

  11. #11
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,548
    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
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with assignment!
    By RVDFan85 in forum C++ Programming
    Replies: 12
    Last Post: 12-02-2006, 11:46 PM
  2. What is the best way to record a process execution time?
    By hanash in forum Linux Programming
    Replies: 7
    Last Post: 03-15-2006, 06:17 AM
  3. time question.
    By InvariantLoop in forum C Programming
    Replies: 5
    Last Post: 02-01-2005, 01:00 PM
  4. inputting time in separate compilation
    By sameintheend01 in forum C++ Programming
    Replies: 6
    Last Post: 03-13-2003, 03:33 AM
  5. time class
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 09:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21