Algorithm Analysis Question

Question

NOTE: I'm ultra-newbie on algorithm analysis so don't take any of my affirmations as absolute truths, anything (or everything) that I state could be wrong.

Hi, I'm reading about algorithm analysis and "Big-O-Notation" and I fell puzzled about something.

Suppose that you are asked to print all permutations of a char array, for [a,b,c] they would be ab, ac, ba, bc, ca and cb.

---

Well one way to do it would be (In Java):

for(int i = 0; i < arr.length; i++)
    for(int q = 0; q < arr.length; q++)
        if(i != q)
            System.out.println(arr[i] + " " + arr[q]);

This algorithm has a notation of O(n²) if I'm correct.

---

I thought other way of doing it:

for(int i = 0; i < arr.length; i++)
    for(int q = i+1; q < arr.length; q++)
    {
        System.out.println(arr[i] + " " + arr[q]);
        System.out.println(arr[q] + " " + arr[i]);
    }

Now this algorithm is twice as fast than the original, but unless I'm wrong, for big-O-notation it's also a O(²)

---

Is this correct? Probably it isn't so I'll rephrase: Where am I wrong??

Answer 1

You are correct. O-notation gives you an idea of how the algorithm scales, not the absolute speed. If you add more possibilities, both solutions will scale the same way, but one will always be twice as fast as the other.

O(n) operations may also be slower than O(n^2) operations, for sufficiently small 'n'. Imagine your O(n) computation involves taking 5 square roots, and your O(n^2) solution is a single comparison. The O(n^2) operation will be faster for small sets of data. But when n=1000, and you are doing 5000 square roots but 1000000 comparisons, then the O(n) might start looking better.

Answer 2

I think most people agree first one is O(n^2). Outer loop runs n times and inner loop runs n times every time outer loop runs. So the run time is O(n * n), O(n^2).

The second one is O(n^2) because the outer loop runs n times. The inner loops runs n-1 times. On average for this algorithm, inner loop runs n/2 times for every outer loop. so the run time of this algorithm is O(n * n/2) => O ( 1/2 * n^2) => O(n^2).