[Solved]: Are functions in O(n) that are nor in o(n) all in Θ(n)?

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 $c\cdot 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