# What is the runtime of the following code? [duplicate]

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.

• 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? – Winston Ewert Sep 28 '14 at 2:14
• @WinstonEwert I am trying to figure the Big O notation for this code, and I don't know what it is – Armon Safai Sep 28 '14 at 3:15
• 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? – Winston Ewert Sep 28 '14 at 3:19
• 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? – David Richerby Sep 28 '14 at 8:06
• @DavidRicherby I want to know the big o notation for a function of f(n) being number of operations, and n being the size – 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$.
• 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. – Yuval Filmus Sep 28 '14 at 8:34
• 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)$. – Yuval Filmus Sep 28 '14 at 8:40