Quote:Original post by blackdot
Take an array of N floats. For each of those values, go through the array and find the next largest value:

O(N^N)?

No, that's O(N*N), so O(N^2). But actually, the problem can also be solved in O(n*log(n)+n), because you could just sort the Array and then linearly go through it in one sweep to gather the result set.

Notably, the PROBLEM complexity (i.e. the optimal algorithm) is likely to be this "low", whatever algorithm you actually implement may run perform worse. If you sort using bubblesort, you have O(n^2+n).


EDIT: Clarification between problem and algorithm complexity.

[Edited by - Thygrrr on July 28, 2006 4:17:14 AM]

Quote:Original post by ToohrVyk
Evaluating the complexity of an algorithm does not and should not take into account the other algorithms that you could use to achieve the problem.

Yes, that's right. Sorry, I was referring to the problem (as stated below).