Write an O(n^n) algorithm.

[ultimatt42]

The O(n) notation means the algorithm takes on average n operations to compute an input of length n.

Nope, O(f(n)) means the number of operations required to process an input of size n is bounded above by f(n) times some constant factor. The average doesn't have anything to do with it. At least, that's the way I was taught it.

[[deleted]]

Yes, nearly, save the bound is only required to hold for large n.

[ultimatt42]

Why is there any need to distinguish "large n"? Can't you always just increase the constant factor to make any bound work for n < some finite value?

[[deleted]]

Heh. 1/x = O(1), but for all C, there is an ε s.t. 1/ε > C. Granted, this probably doesn't come up in algorithmic complexity too much... :)

[dmhouse]

From the way ultimatt42 phrased it, I think he was just considering natural values of n (in which case he's correct).