1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Time complexity(Big oh)

  1. Mar 5, 2014 #1
    Hi this is my first post and I having an extremely hard time finding time complexity in code
    note: I have had no compsci experience (since it was career change) and the professor only went over this for 30 mins
    1. The problem statement, all variables and given/known data
    What is the time complexity (in Θ –notation) in terms of n ? (the red is what is throwing me off)
    a.sum = 0 ;
    for ( i = 0 ; i < n ; i++ )
    for ( j = 1 ; j < n3 ; j = 3*j )
    sum++ ;
    b.sum = 0 ;
    for ( i = n ; i > 0; i = i/3 )
    for ( j = 0 ; j < n3 ; j++ )
    sum++ ;
    2. Relevant equations

    3. The attempt at a solution
    assignments: sum = 0, i = 0, j = 1, j=3*j : (1+1+3*n)
    conditions: j<n3, i<n: 3*(n+1+n(n3+1)
    increments:i++,sum++; n+n3

    b.(this one I'm taking a big educated guess)
    assignments: sum = 0, i = n, i = i/3, j=0: 1+1+n+n/3
    conditions: j<n3, i>0: n/3+1+n(n3+1)
    increments:j++,sum++; n*n3+n*n3

    and if you can explain to me as if I'm a child that would be great!
    Thank you
    Last edited: Mar 5, 2014
  2. jcsd
  3. Mar 5, 2014 #2
    Careful, the loops for (a) are misleading. You have the right idea for the outside loop -- it'll all just be n. But for the inside, essentially what you do is multiply whatever time complexity you have for the inner loop by the complexity of the outer loop (it looks like you were adding them). An easier case for this is two for loops that are both ##O(n)##. The inner loop goes for ##O(n)## ##n## times, so that becomes ##n \cdot O(n)##, or ##O(n^{2})##.

    Also for (a), consider what happens when j goes up to n3, but each iteration you multiply j by three. How do you think these effects will compare? Try writing out a list of values j will take on.

    For (b), the code in red can be difficult to analyze. If it were instead multiplying by 3 each time, this would be exponential, right? So if you're dividing, then what's the opposite of an exponential function?
  4. Mar 6, 2014 #3
    So is it easier to analyze it by loops? Because I found this method online and the professor did not teach how us to read code as you are describing (he was also using a different format from this problem, but I'm guessing it's analyzed the same?).

    okay so for a. can we look at it this way?
    assignments: sum = 0, i = 0, j = 1, j=3*j : (1+1+3*n) → O(n)
    conditions: j<n3, i<n: n+(n)(3n)3 → O(n4)
    increments:i++,sum++; n+n(n3)


    a.sum = 0 ;
    for ( i = 0 ; i < n ; i++ ) → O(n)
    for ( j = 1 ; j < n3 ; j = 3*j ) →n(3n)3→O(n4)
    sum++ ;
    O(n) + O(n4) → O(n4)

    b.sum = 0 ;
    for ( i = n ; i > 0; i = i/3 ) → 3√n → O(n1/3)
    for ( j = 0 ; j < n3 ; j++ ) → (n1/3)*(n3) → n
    sum++ ;

    thank you for helping me understand
    Last edited: Mar 6, 2014
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted