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?

closed as unclear what you're asking by gnat, amon, Thomas Owens May 22 '18 at 9:38

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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

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

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