Can you explain to me how you get the Big O notation for the runtime of the following snippet of code?

for x = 1 to n
    y = 1
    while y < n
       y = y + y

Can you explain the steps on how you get the big O notation for it? Also why doesn't it matter if there a bunch of statements inside a for loop when calculating the big O notation? Wouldn't the number of operations increase as n gets larger if there are more O(1) statements inside the for loop? Help would greatly be appreciated.

  • $\begingroup$ You've got two questions there. It'd probably be better to split it into two separate questions. As for the first question, can you explain exactly where you are stuck? $\endgroup$ – Winston Ewert Sep 28 '14 at 2:14
  • $\begingroup$ @WinstonEwert I am trying to figure the Big O notation for this code, and I don't know what it is $\endgroup$ – Armon Safai Sep 28 '14 at 3:15
  • 1
    $\begingroup$ I can't help you with that unless I understand where you are stuck. I have no idea how much of Big-O notation you understand, and what you need explained in order to solve this problem. Can you explain anything about what you already know about Big-O, and how that doesn't work in this situation? $\endgroup$ – Winston Ewert Sep 28 '14 at 3:19
  • 1
    $\begingroup$ There is no such thing as "the big O notation for this code." It's like holding up an apple and saying, "What is the digit notation for this apple?" Do you want the diameter expressed as a number? The volume? The weight? A number could be used to measure anything! Big O is a notation for saying how functions grow. With respect to this code, you could use a function to measure how long the code takes to run, how much memory it uses or the value of some variable when the code terminates. Which do you want? $\endgroup$ – David Richerby Sep 28 '14 at 8:06
  • $\begingroup$ @DavidRicherby I want to know the big o notation for a function of f(n) being number of operations, and n being the size $\endgroup$ – Armon Safai Sep 28 '14 at 8:26

Hint: First of all, since the code in the loop doesn't depend on $x$, the running time of the code is $\Theta(n)$ times the running time of the code inside the outer loop. Second, the running time of the code in the inner loop is $\Theta(\ell)$, where $\ell$ is the number of iterations of the while loop, which is the number of times you need to double $1$ until you reach or exceed $n$. Perhaps you can find a formula for $\ell$.

  • $\begingroup$ but what if inside a for loop there are like 5 statements that are O(1) instead of 1 statement. Wouldn't that increase the number of operations by a lot? Cause Ive read that you don't take into account the O(1) statements $\endgroup$ – Armon Safai Sep 28 '14 at 8:31
  • $\begingroup$ All instructions count. The running time is (up to constants) the number of statements executed. If there are 5 statements of some type inside the loop and the loop runs $n$ times, then in total $5n$ statements of that type are run. Just ignore what you read. $\endgroup$ – Yuval Filmus Sep 28 '14 at 8:34
  • $\begingroup$ But don't we take out constants in big-o notation? $\endgroup$ – Armon Safai Sep 28 '14 at 8:38
  • $\begingroup$ Yes, we don't care about constants, so for us $5n = \Theta(n)$, or if you're only interested in an $O(\cdot)$ bound, $5n = O(n)$. But the number of statements that are run is exactly $5n$; since each of them takes $O(1)$ to run, we can estimate the running time by $O(n)$. $\endgroup$ – Yuval Filmus Sep 28 '14 at 8:40
  • $\begingroup$ I appreciate the fast responses. But that makes big-o notation so inaccurate then wouldn't it? if it estimates by that much of a difference. Like if there are a million O(1) statements in a for loop, and it would just still be O(n). $\endgroup$ – Armon Safai Sep 28 '14 at 8:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.