Worst case vs O(n)

Is there a difference between statement "Worst case running time of an Al开发者_运维技巧gorithm A" and "Running time of an Algorithm A is O(n)"?

What I think "there is no difference" because, worst case is the peak running time that the function can take, O(n) means that the function is "bounded by". Both give the same meaning.

Hope my logic is correct.

There is difference.

An algorithm is O(f) is not precise: you must say an alogirthm is O(f) in its best/worst/avarage case. You can say that is O(f) when best, worst and avarage are the same, but that's not so common.

I agree with your sentiment, but there are common algorithms (quicksort for instance) that have an expected time much better than their worst case time. You could claim quicksort is O(N^2) worst case, but you still expect it to be O(N*log N) almost always (at least for a good implementation).

It also gets complicated with algorithms that have amortized behavior. You might get O(N) or O(log N) for one particular operation, but many operations in a row will always be O(1) in the amortized sense. Splay trees and Finger trees are good examples in this category.

Running time as an absolute measure is usually less important than how that time increases when you add more data. For example, an algorithm that always takes 5 seconds to process 100 items, 10 seconds to process 200 items and so on, is said to be O(N) since the running time increases linearly with the dataset size. If a second algorithm took 5*5 = 25 seconds to process those 200 items instead, it might be classed as O(N^2). There's no "peak running time" here, since the running time always increases when you throw more data at it.

In fact, big O is an upper bound - so you could say the first algorithm was O(N^2) as well (if N is an upper bound, N*N is higher and hence also an upper bound, albeit a looser one). Common notation to denote other bounds includes Ω (omega, lower bound) and Θ (theta, simultaneous lower and upper bound).

Some algorithms (for instance, Quicksort) exhibit different behaviour depending on the data fed to it - hence the worst case is O(N^2) even though it usually behaves as if it were O(N log N).

There is a huge difference between those strings of words. "Worst case running time of an Algorithm A" is a noun clause, it makes no statement at all. "Running time of Algorithm A is O(n)" is a sentence, telling us something about A.