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: Big-Oh Notation

  1. Oct 29, 2012 #1
    1. The problem statement, all variables and given/known data
    Determine the complexity of the following code:

    Code (Text):
    for (i = 0; i < 2*n; i += 2)
       for (j=n; j > i; j--)

    3. The attempt at a solution
    Well.. The first for block is O( n ) because i is incremented by 2 each loop up to 2n. The second block is O( logn ) as the number of runs gets smaller as j increases.

    So.. the whole algorithm is O( n log n ).

    Any help is appreciated, I'm pretty bad with Big-Oh notation
  2. jcsd
  3. Oct 30, 2012 #2

    The thing we are counting is how many times "a++" is executed. The inner loop causes it to execute (n-i) times.

    The outer loop iterates through values of i in 0,2,4,..2n-2. But the inner loop does not run at all if i>=n. So actually the inner loop only runs for values of i in 0,2,4,n-1, i is even.

    Now count how many times "a++" is executed.

    Ʃ (n-i) for values of i from 0 to n-1, i is even.

    You don't actually have to perform the summation to know it is O(n2). This is because you'll be adding something up like (n=10): 10+8+6+4+2 = 2*(5+4+3+2+1). What's the formula for adding numbers from 1..n?

    Another way you could have guessed it is you've spotted the outerloop is O(n). The inner loop is also O(n) since the number of iterations is a function of (n-i). So the total number of inner loop iterations is O(n*n).

    For O(lg N) you need to see exponential decay in each iteration... something like the number of iterations on the inner loop decrease by a half, third, whatever in each outer loop iteration. To prove these things, you need to count.
    Last edited: Oct 30, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook