Yesterday I started reading "An Introduction To The Analysis of Algorithms" by Sedgewick/Flajolet. For me it was not clear what he meant with "theory of algorithms" and the "scientific approach". I googled a bit and found someone who had the same question:
Until then I thought that I had a good understanding of what worst-case complexity of an algorithm is and how it relates to $O()$ but I think that I was a bit wrong.
In the upper thread someone commented: "(BTW O(), Ω(), Θ() as used in CLRS are about upper, lower and tight bounds all on the worst-case running time, they are not about worst-case, best-case, average-case.)"
And then I was confused. Let split this up in worst-case analysis of a problem and worst-case analysis of a specific algorithm.
Worst-case analysis of a problem
When you have a problem B you want to solve, than it is absolutely understandable that you can have an upper and lower bound on the worst-case complexity since there are numerous algorithms for problem B which all can have different worst-case complexities.
In this case one could say:
The worst-case complexity of problem B lies in O(f(n)) if there is an algorithm for problem B whose worst-case runtine complexity lies in O(f(n)).
The worst-case complexity of a problem B lies in Ω(f(n)) if there can't be (yeah this has to be rigorously proved) an algorithm for the problem B whose worst case complexity lies not! in Ω(f(n)).
A good example is the proof in CLRS that the worst-case complexity of sorting(via comparing) lies in Θ(n log(n)).
So now to the worst-case complexity of an algorithm.
Worst-case analysis of an algorithm
Lets say we have an algorithm A for some problem and want to find out something about the worst-case complexity of A. For the upper bound I just have to find out for which problem instances the algorithm A has to do the most steps or the most "work".
So here is my problem: What should the lower bound on the worst-case complexity of an algorithm A be?
There is only one way which for me could explain that. If every algorithm yields several different implementations than one could really define a lower bound on the "best" worst-case complexity on all possible implementations of this algorithm A.
If everything what I wrote here is right for the most part than I have to say, that a lot! of books deal extremely sloppy with the relation between the asymptotic analysis and the best-,average and worst-case runtime.