3
$\begingroup$ 
    i<--2
    while (i<n)
      someWork (...)
      i <-- power (i,2)
    done

Given that someWork(...) is an O(n) algorithm, what is the worst case time complexity?

I've found this question answered on this site with the solution of O(n log n), however I don't quite understand why. I know that the power function has O(log n), but I don't understand why the overall Big O of the loop becomes O(n log n) instead of just O(n). Can someone please explain this to me?

Improve this question
$\endgroup$
6
  • $\begingroup$ You should clarify your question by including all the code, what does ... represent? is someWork(...) just a function call, or is it a declaration? $\endgroup$
    – hellaFont
    Jul 5, 2014 at 3:11
  • 1
    $\begingroup$ Sorry, I believe someWork(...) is just a function call. This was all the pseudocode that was included in the question given to me. $\endgroup$
    – user3806894
    Jul 5, 2014 at 3:12
  • $\begingroup$ What have you tried? What are your thoughts? We want to clear up your confusions, not just solve your problem for you. Have you tried computing how many times the loop will iterate? how long each iteration will take? Have you read our reference questions on the topic, e.g., cs.stackexchange.com/q/192/755, cs.stackexchange.com/q/23593/755? This is covered there. A problem dump like this is usually not considered a great fit for this site. $\endgroup$
    – D.W. ♦
    Jul 16, 2014 at 16:50
  • $\begingroup$ In fact, your question is answered by the second answer to this question: How to come up with the runtime of algorithms?, so I'm going to vote to close as a duplicate. $\endgroup$
    – D.W. ♦
    Jul 16, 2014 at 16:52
  • 1
    $\begingroup$ @D.W. The whole premise of stackexchange sites is that there is value in answering questions on a specific case-by-case basis. That thread is very generic - one might as well just refer to a book instead, which contains the same material. $\endgroup$
    – Nick Alger
    Jul 16, 2014 at 17:34

2 Answers 2

Reset to default
1
$\begingroup$

You're missing a very crucial component of Big-Oh analysis. That question is: given some number n and some code p how does the MAXIMUM runtime of p(n) differ with respect to time per each n -- that is, what are the bounds of p(n) with respect to n. When code tracing, create a tally.

Here, we see that i is initialized to 2. Then the code enters into a while loop. Then, while i<n we perform some work n number of times, since we know that someWork(...) has a maximum time complexity of n -- that is, linear time. We add n to our tally.

The next line of code is i gets initialized to i being raised to the power of 2. This variable, i directly impacts the runtime of the loop, since i with respect to n governs the condition upon entering and exiting the loop. We now know that we will perform the loop log(n) times.

Putting it all together, we know that since someWork(...) takes linear time (n) and that we will perform someWork(...) log(n) times, we can compute the tally for the big-oh analysis of the function as n*log(n)

Does this make more sense now?

Improve this answer
$\endgroup$
1
  • $\begingroup$ You seem to be suggesting that $O$ and worst-cases were related; they are not. Cf. our reference question. $\endgroup$
    – Raphael ♦
    Jul 16, 2014 at 23:51
1
$\begingroup$

The loop runs O(log(n)) times since it runs until i > n and each iteration i := i^2.

Assuming someWork() takes O(n) the total run time will be O(nlogn) since you're performing a task that take O(n), O(logn) times (loop).

Improve this answer
$\endgroup$
0