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?

  • $\begingroup$ What do "nested loops" mean? What about the linear time selection algorithm, which is recursive? $\endgroup$ – Yuval Filmus Mar 15 '19 at 8:40
  • 5
    $\begingroup$ 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. $\endgroup$ – xavierm02 Mar 15 '19 at 8:52
  • 3
    $\begingroup$ 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. $\endgroup$ – John L. Mar 15 '19 at 8:53

You can write an interpreter for any reasonable instruction set usin a single loop with a very, very long if/ else if / else if... statement. That should cover about all solvable problems. You can calculate the Ackerman function with one loop without recursion (not in the lifetime of the universe for n >= 4, but in principle).

  • $\begingroup$ So not only $O(n)$ algorithms, but all algorithms can be implemented with one loop? $\endgroup$ – Shreck Ye Mar 16 '19 at 10:17
  • 1
    $\begingroup$ All that can be implemented on any reasonable machine. $\endgroup$ – gnasher729 Mar 16 '19 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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