Problem Detail: One of my lectures makes the following statement: $$( f(n)=O(n) land f(n)neq o(n) )implies f(n)=Theta(n)$$ Maybe I’m missing something in the definitions, but for example bubble sort is $O(n^2)$ and not $o(n^2)$ but it’s also not $theta(n^2)$ since it’s best case run time $Omega(n)$. What am I missing here?
Asked By : Robert S. Barnes
Answered By : Shaull
What you are missing is a very important point: An algorithm is never $O()$ of anything, since it is usually not a even a real-valued function. When we say that bubble-sort is $O(n^2)$, what we mean is that in the function $f$, that represents the worst case run-time of bubble sort, is $O(n^2)$. In this case, this function is indeed $theta(n^2)$, since in the worst case, the run-time is bounded from below and from above by $ccdot n^2$ for the relevant constants $c$. To be more precise, the function that we refer to as the worst case runtime of an algorithm $A$ is defined by $$f_A(n)=max_{x: |x|=n}{text{runtime of $A$ on input x}}$$ And it is this function that we analyze for the worst case run time. The best case run-time can be analyzed as well, of course. As you suggest, the best case run time of bubble sort is not $theta(n^2)$, but rather $theta(n)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10352 Ask a Question Download Related Notes/Documents
