Generating O(N^2) without loops [closed]

Question

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?

Answer 1

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;
    }
}

Answer 2

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".