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

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?

• 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 May 22 '18 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 May 22 '18 at 2:54
• – gnat May 22 '18 at 5:56
• What do you mean by "loops"? – Caleth May 22 '18 at 9:48
• @DavidArno: Eh, it's "explaining code," which is still off-topic here. – Robert Harvey May 22 '18 at 17:02

## 2 Answers

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

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

• Wouldn't it be O(N) because in the worst case, you could get N from user input? – David Klempfner May 23 '18 at 0:58
• @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. – JounceCracklePop May 23 '18 at 20:08