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

Big-O notation says nothing about the speed of the algorithm except for how fast it is relative to itself when the size of the input changes.

An algorithm could be O(1) yet take a million years. Another algorithm could be O(n^2) but be faster than an O(n) algorithm for small n.

Some of the answers to this question may help with this aspect of big-O notation. The answers to this question may also be helpful.

Answer 3

One way of thinking about Big O is to consider how well the different algorithms would fare even in really unfair circumstances. For instance, if one was running on a really powerful supercomputer and the other was running on a wrist-watch. If it's possible to choose an N that is so large that even though the worse algorithm is running on a supercomputer, the wrist watch can still finish first, then they have different Big O complexities. If, on the other hand, you can see that the supercomputer will always win, regardless of which algorithm you chose or how big your N was, then both algorithms must, by definition, have the same complexity.

In your algorithms, the faster algorithm was only twice as fast as the first. This is not enough of an advantage for the wrist watch to beat the supercomputer, even if N was very high, 1million, 1trillion, or even Graham's number, the pocket watch could never ever beat the super computer with that algorithm. The same would be true if they swapped algorithms. Therefore both algorithms, by definition of Big O, have the same complexity.

Answer 4

Ignoring the problem of calling your program output "permutation":

Big-O-Notation omits constant coefficients. And 2 is a constant coefficient.

So, there is nothing wrong for programs two times faster than the original to have the same O()

Answer 5

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

Answer 6

You're right about them both being big-O n squared, and you actually proved that to be true in your question when you said "Now this algorithm is twice as fast than the original." Twice as fast means multiplied by 1/2 which is a constant, so by definition they're in the same big-O set.

Answer 7

Suppose I had an algorithm to do the same thing in O(n) time. Now also suppose I gave you an array of 10000 characters. Your algorithms would take n^2 and (1/2)n^2 time, which is 100,000,000 and 50,000,000. My algorithm would take 10,000. Clearly that factor of 1/2 isn't making a difference, since mine is so much faster. The n^2 term is said to dominate the lesser terms like n and 1/2, essentially rendering them negligible.

Answer 8

You are correct. Two algorithms are equivalent in Big O notation if one of them takes a constant amount of time more ("A takes 5 minutes more than B"), or a multiple ("A takes 5 times longer than B") or both ("A takes 2 times B plus an extra 30 milliseconds") for all sizes of input.

Here is an example that uses a FUNDAMENTALLY different algorithm to do a similar sort of problem. First, the slower version, which looks much like your original example:

boolean arraysHaveAMatch = false;
for (int i = 0; i < arr1.length(); i++) {
    for (int j = i; j < arr2.length(); j++) {
        if (arr1[i] == arr2[j]) {
            arraysHaveAMatch = true;
        }
    }
}

That has O(n^2) behavior, just like your original (it even uses the same shortcut you discovered of starting the j index from the i index instead of from 0). Now here is a different approach:

boolean arraysHaveAMatch = false;
Set set = new HashSet<Integer>();
for (int i = 0; i < arr1.length(); i++) {
    set.add(arr1[i]);
}
for (int j = 0; j < arr2.length(); j++) {
    if (set.contains(arr2[j])) {
        arraysHaveAMatch = true;
    }
}

Now, if you try running these, you will probably find that the first version runs FASTER. At least if you try with arrays of length 10. Because the second version has to deal with creating the HashSet object and all of its internal data structures, and because it has to calculate a hash code for every integer. HOWEVER, if you try it with arrays of length 10,000,000 you will find a COMPLETELY different story. The first version has to examine about 50,000,000,000,000 pairs of numbers (about (N*N)/2); the second version has to perform hash function calculations on about 20,000,000 numbers (about 2*N). In THIS case, you certainly want the second version!!

The basic idea behind Big O calculations is (1) it's reasonably easy to calculate (you don't have to worry about details like how fast your CPU is or what kind of L2 cache it has), and (2) who cares about the small problems... they're fast enough anyway: it's the BIG problems that will kill you! These aren't always the case (sometimes it DOES matter what kind of cache you have, and sometimes it DOES matter how well things perform on small data sets) but they're close enough to true often enough for Big O to be useful.

Answer 9

The big-oh notation express a family of function, so say "this thing is O(n²)" means nothing

This isn't pedantry, it is the only, correct way to understand those things.

O(f) = { g | exists x_0 and c such that, for all x > x_0, g(x) <= f(x) * c }

Now, suppose that you're counting the steps that your algorithm, in the worst case, does in term of the size of the input: call that function f. If f \in O(n²), then you can say that your algorithm has a worst-case of O(n²) (but also O(n³) or O(2^n)). The meaninglessness of the constants follow from the definition (see that c?).

Answer 10

The best way to understand Big-O notation is to get the mathematical grasp of the idea behind the notation. Look for dictionary meaning of the word "Asymptote"

A line which approaches nearer to some curve than assignable distance, but, though
infinitely extended, would never meet it.

This defines the maximum execution time (imaginary because asymptote line meets the curve at infinity), so what ever you do will be under that time.
With this idea, you might want to know, Big-O, Small-O and omega notation.