What the heck is O(log2) and stuff like that?

[AutoDMC]

I read this post in another forum:

Looks a bit like Dijkstra's to me, Dijkstra's also searches in a circular way. With an heap it can reach speeds of O(|E|log|V|) (E=edge V=vertex) while it seems like your path algorithm still has a speed of O(|V|2) (I may be wrong though). If you need speed on large maps you might look into A* (a 'smart' variant on Dijkstra's).

I remimber seeing questions like this on a C++ competition I took place in out here where I live. I asked my Computer Science teacher what it was, and he hadn't a clue.

The thing looks something like O(*math stuff here*), and is used to describe the amount of time it takes to solve a function.. I think.

Could somebody explain WHAT the O(*****) means, and how to use it, and how to understand it?

Thanks. I've been wanting to know for about 2 years now. But it's problebly on the bottom of my gotta research list

[jox]

It describes the curve of how the complexity of algorithms rises dependent from given parameters.

That means if you have an algorithm that has complexity O(N) then its linear. If, say, with N=1 the algorithm needs 1 second, then it will need 10 seconds with N=10. With O(N^2) it will raise exponential. The higher N is the slower it will get. And so on.

[AutoDMC]

Ahh, thanks! (I thought it was something like that, but I wasn't sure!)

[hybrid]

It describes the curve of how the complexity of algorithms rises dependent from given parameters.

That means if you have an algorithm that has complexity O(N) then its linear. If, say, with N=1 the algorithm needs 1 second, then it will need 10 seconds with N=10. With O(N^2) it will raise exponential. The higher N is the slower it will get. And so on.

Sorry, but I have to add minor correction here. With O(N^2) its growing polynomial, while its exponential with O(2^N). Also note that the O-notation hides any factor which does not make the growing belong to a strictly larger class. Thus, the class O(2*N) is the same as O(N) since the constant factor still leaves complexity within bounds of linear growth.
You can also have more than one variable inside the expression as used in the first example (E and V are variables).
As a rule of thumb all polynomial algorithms become intractable when some serious amount of data is handled, while exponential algorithms are intractable by definition. The largest class of algorithms which should be usable even on large input data is O(N*log N). You will, however have to check for average and worst execution times in order to be satisfied with your results A common example are sorting algorithms where the better ones have an average execution time of O(N*log N) while worst execution times are often polynomial.
Of course, all of this only holds until somebody will prove that P=NP because this would mean that expontential algorithms could be solved in polynomial time...

[jox]

Thanks hybrid for the addition, and sorry for my inaccuracy.