Thread: Big-O Question

If you have a random access container, you can look up any item in it directly without any looping (O(1)). A linked list does not have random access - so to access n-th element you have to start from the beginning and follow the links until you get there (and the time it takes is proportional to how far in the list you need to go).

If the list has size and at methods, you bet there would be a lot going on in this simple loop:

Code:

for (int i = 0; i < myList.size(); ++i) {
    myList.at(i);
}

the place in memory of any list element is only given by the place of the preceding and/or the subsequent element (depends on the type of list). Every element has a field that points to the neighbour.
So if you "have" a list, you have the memory address of its first element.
To access any other element, you have to walk from the first one step by step till you reach it. If you are unlucky, that are n steps. So O(n) is the execution time in the worst case. In the average case it's O(n/2) and in the best case O(1). Most times the average case is referenced. But O(n/2) is the same quarantining as O(n) - computer science people ignore that difference because execution times of O(n/2) and O(n) belongs to the same class of problems.

For a vector, the address of any element is always known directly, you doesn't need to care about other elements to look one up. So lookup is O(1) always. best, average and worst.

O(1) is the best you can get from any algorithm. This can only be further accelerated by a linear speedup, but even than does it stay O(1). Programmer want O(1) stuff, but the get it seldom.
Many important things are O(log n) which is also acceptable most times.
Next best is often O(n). For big data sets you should get a newer cpu for that.
Than comes O(n^2) ... O(n^3) ... keep cooking coffee
And O(n^n): you should really really look for alternatives to this one

O(n/2) and O(n) are exactly the same. The formal definition of O(f(n)) time is that the ratio of the actual running time (as a function of n), to f(n) is bounded by some constant. The definition is rigged so a constant factor doesn't make any difference.

http://en.wikipedia.org/wiki/Big-O_n...mal_definition

Edit: I should have said "bounded by some constant, as n goes to infinity".

Originally Posted by sh3rpa

One to avoid:

O(n!)

Yes! Avoid if at all possible!

--
Mats

Originally Posted by anon

If you have a random access container, you can look up any item in it directly without any looping (O(1)). A linked list does not have random access - so to access n-th element you have to start from the beginning and follow the links until you get there (and the time it takes is proportional to how far in the list you need to go).

If the list has size and at methods, you bet there would be a lot going on in this simple loop:

Code:

for (int i = 0; i < myList.size(); ++i) {
    myList.at(i);
}

I wrote the line being quoted in the OP. I shall punctuate it better etc:
Any O(n) running-time, list-accessor, is fundamentally wrong, as it encourages writing horribly inefficient code.
Could be too many commas now though.

Yeah O(n) is Big-Oh notation and n corresponds to the number of items in the list.
The code anon shows above is exactly why one should not have an accessor that take O(n) running time, where n is the number of items in the list.
Accessors should really be O(1) or O(log(n)). O(sqrt(n)) is probably borderline unacceptable. O(n) is just too slow, and anything worse, like O(n*n) is a total abomination.

You said it before, and you've said it again. That doesn't make you right, or any less wrong.

How about if more people say it?

Any O(n) "random-access" function is fundamentally wrong. Such a thing is not random-access.

If random access is so infrequent that you can accept O(n) for it, you can accept writing *std::advance(cont.begin(), n) to get there. At least it will make you remember that it is O(n), and if you use it too often, you'll switch to a container that supports it efficiently.