# Can all $O(n)$ problems be solved without nested loops?

There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a question, can all such implementations be simplified or converted to an implementation with only top layer loops? Namely, can all problems that have an $$O(n)$$ algorithm be solved with an algorithm without nested loops?

• What do "nested loops" mean? What about the linear time selection algorithm, which is recursive? – Yuval Filmus Mar 15 '19 at 8:40
• For any algorithm, you can find another algorithm with a single loop that computes the same thing. The idea is that if you keep an integer of "where you are in the original program", and in the unique loop, you have a big case analysis on this integer. This allows to simulate jumps (by changing the integer) and therefore loops. – xavierm02 Mar 15 '19 at 8:52
• It might be a surprise to you, but "nested loop" is not a well-defined concept although it looks like very clear intuitively. For example, Turing machine is defined without any reference to a loop. – John L. Mar 15 '19 at 8:53

• So not only $O(n)$ algorithms, but all algorithms can be implemented with one loop? – Shreck Ye Mar 16 '19 at 10:17