1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Asymptotic running time of code segments

  1. Oct 29, 2014 #1
    I'm trying to grasp some basic concepts of analyzing code segments. Not sure if I have the right thought process. Can't find many examples online.

    1. The problem statement, all variables and given/known data

    A.)
    for (i=1; i<n; i++)
    for (j=1; j<n; j++)
    return 1

    Guess: Theta(n) because both loops go to (n) and they're independent? or is it constant because it's only doing a constant bit of work?

    B.)
    for (i=1; i<n; i++)
    for (j=1; j<log n; j++)
    A[j] = 3A[j]

    Guess: Theta(n) because the outer loop goes to (n)?

    C.)
    for (i=1; i<5; i++)
    for (j=1; j<i; j++)
    A[j] = 0

    Guess: Theta(1) because it executes in constant time?

    D.)
    for (i=1; i<5; i++)
    for (j=1; j<i; j++)
    i = n

    Guess: Theta(1) because it executes in constant time?

    E.)
    x = n
    while (x > 1)
    x = x/2

    Not sure how to do this

    F.)
    x = 1
    while (x<n)
    x = x+3

    Not sure how to do this either.

    2. Relevant equations

    3. The attempt at a solution


    I put the attempts in part 1 because it's easier to follow. Any help would be appreciated, thanks.
     
  2. jcsd
  3. Oct 29, 2014 #2

    Mark44

    Staff: Mentor

    Is this C code? If so, you're missing a semicolon on the return statement. Also, in the code I copied I see some indentation that doesn't show up in your first post. When you post code, please put a [ code ] tag at the top of it, and a [ /code ] tag at the bottom, without the extra spaces that I showed. That will preserve your indentation. I have put your first example in the code tags, and I have also added a semicolon in the return statement.
    Code (Text):
    for (i=1; i<n; i++)
        for (j=1; j<n; j++)
         return 1;
     
    The real question is how many times does the inner loop body run?
     
  4. Oct 30, 2014 #3

    Zondrina

    User Avatar
    Homework Helper

    With the code modifications Mark suggested in his post, the code in part A) should properly run. The fact the return statement is inside the inner loop means the code will execute in ##O(1)## time (due to early exit). Pretending the return statement isn't there though will yield a much more interesting result. Suppose the code reads:

    Code (Text):

    for (i=1; i<n; i++)
        for (j=1; j<n; j++)
     
    When the first iteration for ##i## occurs, you know the inner ##j## loop will execute until ##j < n##. This results in a ##O(n-1) = O(n)## run time for the inner loop since ##j## began at one (hence the inner loop executes ##n-1## times).

    The second iteration for ##i## will then occur, and the inner ##j## loop will once again execute. Again this results in ##O(n-1) = O(n)## run time for the inner loop.

    This means by the time the outer loop executes ##n-1## times, the code will have taken ##O(n^2)## time to have run.

    Proof: ##T(n) = (n - 1)*(n-1) = n^2 - 2n + 1 \leq n^2 + 1 \leq 2n^2## for ##n \geq 1##.

    Hence ##T(n) \leq 2n^2 = kf(n)##. So you could conclude ##T(n) = O(n^2)##.

    I hope this example will help with your other code snippets.

    EDIT: I forgot to mention something if you were looking for ##\Theta## of the code run time. The code will execute in ##\Omega(n^2)## time at best.

    Since it executes with the same efficiency in the best and worst case scenario (i.e ##T(n) = O(n^2) = \Omega(n^2)##), it can be concluded ##T(n) = \Theta(n^2)##.
     
    Last edited: Oct 30, 2014
  5. Oct 30, 2014 #4

    Zondrina

    User Avatar
    Homework Helper

    Part E) and F) are good examples even though they have ##while## loops instead.

    For ##E)## I think you are meant to assume that ##x## is of type ##float \space / \space double##, otherwise the code would not be very interesting (integer division is a problem).

    You need to consider what happens when ##n \leq 2##. This is quite trivial and produces an expected ##T(n) = \Omega(1)## at best.

    If ##n \geq 3## you can start getting an upper bound on the code. It's clear to see that ##\Theta## will not be definable since ##\Omega(1) \neq O(?)##.
     
  6. Oct 30, 2014 #5
    It's actually supposed to be "pseudo-code". Appreciate the help guys

    So for B, would it be theta (n) because the outer loop dominates? And C is theta(1)?

    but for D, how could we answer this if we don't know what 'n' will be? Everything I posted is everything I was given in the question
     
  7. Oct 30, 2014 #6

    Mark44

    Staff: Mentor

    How is integer division a problem?
     
  8. Oct 30, 2014 #7

    Zondrina

    User Avatar
    Homework Helper

    If ##n = 3##, then on the first iteration ##x## will get set to ##3/2 = 1.5##. If ##x## is an int, then the ##0.5## will be truncated, and ##x = 1##. This is a different result than what I think was intended.

    Continuing the pattern using a precision type, you would expect ##O(\frac{n}{2})##.
     
  9. Oct 31, 2014 #8

    Mark44

    Staff: Mentor

    That's not how integer division works. Using integer division, 3/2 == 1. There is no fractional part, so no fractional part gets truncated.
    Which is what you get with either type of division. My point is that raising a question of which type of division is being performed is irrelevant, not to mention that the OP tells us that this is pseudocode, so fine points of integer division vs. floating point division aren't germane to the discussion.
     
  10. Oct 31, 2014 #9

    Zondrina

    User Avatar
    Homework Helper

    I disagree entirely.

    For ##n == 3##, you would expect two iterations. One for 3 and one for 1.5, but if ##x## is an int, you're only going to get one iteration, namely for 3.

    For ##n == 4##, you obviously know two iterations will happen, and that works fine either way.

    For ##n == 5##, you expect three iterations. One for 5, 2.5 and 1.25 respectively. If ##x## is an int, you're only going to get an iteration for 5 and 2 respectively.

    For ##n == 6##, same deal as ##n == 4##. You expect three iterations.

    For ##n == 7##, you expect three iterations for 7, 3.5, 1.75. If ##x## is an int, you get an iteration for 7 and 3.

    For ##n == 9##, you expect four iterations for 9, 4.5, 2.25, 1.125. If ##x## is an int, then you only iterate for 9, 4, 2.

    Clearly whether or not ##x## is an int is significant to the outcome.

    Although I agree if the code is pseudo code, specifics like these shouldn't matter too much. I just felt as if it's relevant to the understanding.
     
  11. Oct 31, 2014 #10

    Mark44

    Staff: Mentor

    I think you're missing the point of the exercise, which is to analyze the time behavior of the loops, in general, not for specific small values of n. Since the examples are given in pseudocode, it's not reasonable to assume that division follows rules that are peculiar to programming languages that are derived from C. The whole business of how division is performed is a red herring, IMO.
     
    Last edited: Oct 31, 2014
  12. Oct 31, 2014 #11
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Asymptotic running time of code segments
Loading...