patternModerate
Are functions in O(n) that are nor in o(n) all in Θ(n)?
Viewed 0 times
allarethatnorfunctions
Problem
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?
$$( 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?
Solution
Tell the lecturer they're wrong. Take the function
$$ f(n) = \begin{cases} n & n \text{ is even}, \\ 1 & n \text { is odd}. \end{cases} $$
This function is $O(n)$ but neither $o(n)$ nor $\Theta(n)$.
Here is a monotone example, which might be more convincing:
$$ g(n) = \exp \exp \lfloor \ln \ln n \rfloor. $$
$$ f(n) = \begin{cases} n & n \text{ is even}, \\ 1 & n \text { is odd}. \end{cases} $$
This function is $O(n)$ but neither $o(n)$ nor $\Theta(n)$.
Here is a monotone example, which might be more convincing:
$$ g(n) = \exp \exp \lfloor \ln \ln n \rfloor. $$
Context
StackExchange Computer Science Q#10352, answer score: 15
Revisions (0)
No revisions yet.