# Not sure what do Nielsen and Chuang mean by number of operations

I am reading Nielsen and Chuang's "Quantum Computation and Quantum Information". One important concept about algorithms is how the number of operations scales with the length of the input. I realized I might not be getting what they actually mean by this in Exercise 5.17:

Part (1) is OK. In part (2) I think there is a typo. According to the answer to this question, it should read "$$y=\log_2 N$$" rather than just "$$\log_2 N$$". Then, what I understand the algorithm is doing in that step is computing $$x=\log_2N/b$$ for each $$b \leq L$$. These are $$O(L)$$ operations rather than $$O(L^2)$$ as it claims. Where are the other $$O(L)$$ operations?

I have thought perhaps these numbers don't agree because you have to take into account the number of operations required for elementary mathematical operations (see e.g. here), and computing $$2^x$$ takes more than one operation. But if I take into account the complexity of $$2^x$$, then I should also take into account the complexity of division in $$x = \log_2 N/b$$. Moreover, I don't think they are referring to this, because I have read all the chapters until here and I don't remember that they have explained this.

• The complexity class O(L^2) includes O(L) as a subset. If you're using L operations, that's still in O(L^2) it just also happens to be in O(L). Commented Apr 3, 2020 at 18:31
• @CraigGidney yes, of course, but do you think that's what they mean by "at most $O(L^2)$ operations"? Why would they write $O(L^2)$ when you can write $O(L)$? Commented Apr 3, 2020 at 18:35
• In order to make the exercise easier. Commented Apr 3, 2020 at 22:59