2

I understand you can generate an O(N^2) algorithm by using loops:

eg:

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
    {
        //do something N^2 times.
    }
}

Is it possible to generate an O(N^2) without using loops (for, foreach, while, goto)? How would you do it?

8
  • 2
    Recursion. Some kind of naive version of merge sort could be O(n^2) without a double loop. There is probably some kind of recursive algorithm that is n^2 without using any loops but I can't think of an example which isn't completely inane.
    – Turksarama
    Commented May 22, 2018 at 2:26
  • I believe it's up to your circumstance. Some cases have to use O(n^2) for the solution, I work on sync lot of data between 2 systems and it's use loop in loop alot (have to upgrade RAM 64GB and 1000GB SDD). For general, it you want to break and O(n^2), the case must have a special point.
    – Felix
    Commented May 22, 2018 at 2:54
  • Possible duplicate of General way to convert a loop (while/for) to recursion or from a recursion to a loop?
    – gnat
    Commented May 22, 2018 at 5:56
  • What do you mean by "loops"?
    – Caleth
    Commented May 22, 2018 at 9:48
  • 1
    @DavidArno: Eh, it's "explaining code," which is still off-topic here. Commented May 22, 2018 at 17:02

2 Answers 2

6

Here's a somewhat contrived example, squaring a number using recursion and no loops.

using System;

public class Program
{
    public static void Main()
    {
        var num_to_square = 10;
        Console.WriteLine(square(num_to_square)); //100
    }

    public static int square(int n)
    {
        return recurse(n-1, n-1);
    }

    private static int recurse(int x, int y)
    {
        int c = 1;
        if (x + y == 0)
        {
            return c;
        }

        c += recurse(x - 1, y);
        if (x == y)
        {
            c += recurse(x - 1, y - 1);
        }

        return c;
    }
}
5

No.* Any algorithm with no loops must be O(1), because you know at compile-time how many steps the algorithm will take (at most).

Unless by "using a loop" you mean actually writing one of the C# iteration statements: for, foreach, do, or while. Then of course there are other ways, but I'd argue they're all just different ways of making a loop. For instance:

i = 0;
Outer:
    j = 0;
    Inner:
        //do something N^2 times.
        j++;
        if (j < N) {
            goto Inner;
        }
    i++;
    if (i < N) {
        goto Outer;
    }

That's your same loop written with goto. Or how about this:

Enumerable.Range(0, N).SelectMany(i =>
    Enumerable.Range(0, N).Select(j => { /*do something N^2 times*/ })
).ToList();

There's the same loop using Enumerable methods and extensions. Does it count if the implementation of ToList uses a loop?

*Depending on how you count recursion

There's certainly an argument to be made that recursion is just plain "different" from iteration, but every recursive algorithm can be converted into an equivalent iterative one. In fact it would be perfectly reasonable for a compiler to do this. Does your algorithm "use a loop" if it is logically equivalent to an algorithm which uses a loop? It just depends on exactly what you mean by "algorithm".

2
  • Wouldn't it be O(N) because in the worst case, you could get N from user input? Commented May 23, 2018 at 0:58
  • 2
    @Backwards_Dave Wouldn't what be O(N)? An algorithm with no loops? No, it must be O(1). To see why, write the execution steps of the algorithm as a directed graph. A loop is a cycle in the graph. With no cycles, there is a finite-length longest possible path through the graph, and no input can make it longer. Commented May 23, 2018 at 20:08

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