What is the relation/difference between worst case time complexity of an algorithm and its upper bound? -
what relation/difference between worst case time complexity of algorithm , upper bound?
the term "upper bound" not clear, may refer 2 possible things:
the upper bound of algorithm - bound algorithm can never run "slower" it. worst case performance of it, if mean - answer pretty simple.
big-o notation, provides upper bound on complexity of algorithm under specific analysis. big-o notation set of functions, , can applied analysis of algorithm, including worst case, average case, , best case.
let's take quick sort example.
quick sort said have o(n^2) worst case performance, , o(nlogn) average case performance. how can 1 algorithm has 2 complexities? simple, function representing analysis of average case, , 1 representing worst case, different funcitons - , can apply big o notation on each of them, there no restriction it.
moreover, can apply best-case. consider small optimization quick-sort, first checks if array sorted, , if - stops immidiately. o(n) operation, , there input provide behavior - can algorithm's best case complexity o(n)
