Thread: Running time analysis

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    28

    Running time analysis

    Code:
    sum=0;
    for (i=1; i<=n; i*=2)
    for (j=1; j<=i; j++)
    sum++;
    
    r=0
    for(i=1; i<= n ; i++)
    for (j = 1; j <= n; j*=2)
    if (n mod 2 == 0) // n even 
    for (k = 1; k <= n; k++)
    r++;
    else // n odd
    r--;
    how to calculate the running analysis for the worst case of the two above algorithms??

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Please change your [\code] tag - replace the \ with /, and it will show your code correctly.

  3. #3
    Registered User
    Join Date
    Sep 2011
    Posts
    28
    Code:
    sum=0;
    for (i=1; i<=n; i*=2)
    for (j=1; j<=i; j++)
    sum++;
    
    r=0
    for(i=1; i<= n ; i++)
    for (j = 1; j <= n; j*=2)
    if (n mod 2 == 0) // n even
    for (k = 1; k <= n; k++)
    r++;
    else // n odd
    r--;
    good point

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Ok... you found the code tags... now learn how to indent your code...

    Indent style - Wikipedia, the free encyclopedia

  5. #5
    Registered User
    Join Date
    Sep 2011
    Location
    Stockholm, Sweden
    Posts
    131
    This should do the trick:

    Code:
    clock_t t0, t1, elapsed;
    t0 = clock();
    /* Code to clock goes here */
    t1 = clock();
    elapsed = 1000 * (t1 - t0) / (CLOCKS_PER_SEC);
    printf("Avg elapsed time: %ld ms\n\n", elapsed/MAX_LOOPS);

  6. #6
    Registered User
    Join Date
    Sep 2011
    Posts
    28
    How can i analyze the time that needs the program to be executed? is it all about maths?

  7. #7
    Registered User
    Join Date
    Sep 2011
    Location
    Stockholm, Sweden
    Posts
    131
    Quote Originally Posted by antros48 View Post
    How can i analyze the time that needs the program to be executed? is it all about maths?
    Do you mean that you want to estimate how long it will take to run in advance?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by antros48
    How can i analyze the time that needs the program to be executed? is it all about maths?
    Are you talking about the run time complexity of those snippets of code? Then yes, it is more or less about counting and maths. Go through the algorithm with specific input to understand what is happening. Count to give yourself a ballpark estimate of how the number of operations might vary with the size of the input, if only for the average case at first.

    Since this is not about C, I am moving this thread.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    In the first example you have a loop of order n, and within this loop is another loop of order n (it loops to i, which itself is order n), making the total O(n^2).

    In the second example you have a loop of order n, and within this loop another loop of order n, and within THAT loop, you get ANOTHER loop of order n, every other time, which makes the whole thing O(n^3).
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    for (i=1; i<=n; i*=2)
    Is this really a loop of order n, and not perhaps of log(n)?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Beam or Frame Analysis for Structural Analysis
    By greenmania in forum C Programming
    Replies: 3
    Last Post: 05-05-2010, 05:40 PM
  2. Running time
    By wu_weidong in forum Tech Board
    Replies: 1
    Last Post: 09-05-2005, 04:03 PM
  3. Help !!! Time is running out !!!
    By khpuce in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 02-14-2005, 11:57 AM
  4. Replies: 3
    Last Post: 06-13-2003, 06:47 AM
  5. running time
    By Unregistered in forum C++ Programming
    Replies: 5
    Last Post: 01-16-2002, 09:35 AM