Problem Detail: The following is an excerpt from CLRS:
$Theta(g(n))= { f(n) mid text{ $exists c_1,c_2,n_0>0$ such that $0 le c_1 g(n) le f(n) le c_2g(n)$ for all $n ge n_0$}}$.
Assuming $n in mathbb{N}$, I was unable to find $f(n)$ and $g(n)$ such that the bound does not apply for all $n$. Note: This question was asked with the flawed assumption that $f(n)$ and $g(n)$ necessarily have natural domains.
Asked By : Farhad Yusufali
Answered By : Juho
You need to have a non-negative sufficiently large input size $n$ from which point on the bound holds. Have a look the Figure 3.1 in CLRS, which shows graphically examples of the $O, Theta$ and $Omega$ notation. You can also see why this makes sense. For example, we are interested in knowing how an algorithm’s runtime behaves as the input gets larger and larger. Thus, we don’t really care too much about small values of $n$. It is not always the case that for every nonnegative $n$ a bound would hold. For example, consider two functions $f(n)=n$ and $g(n)=n log n$. We can plot them for a few small values of $n$. $g(n)$ does not dominate $f(n)$ for all values of $n$. For sufficiently large values of $n$, it will. In other words, $f(n) = O(g(n))$. Note that this is only an upper bound, but the idea will be the same for $Theta$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7281 Ask a Question Download Related Notes/Documents
