I'm thinking no, as sin(n) seems to be a counterexample (it is $\Theta(1)$ but not constant). Are there nontrivial counterexamples (in the sense that they relate to some known algorithm)?
2 Answers
You are right, and sin(n) is a fine counterexample.
An even simpler counterexample is f(n) = n + 1 and g(n) = n.
f(n) is clearly ϴ(g(n)), yet there is no constant c such that
n + 1 = c n for all n.
Since you wanted a counterexample that would relate to the running time of a real algorithm, this one should do fine (e.g. looping from 1 to n vs. looping from 1 to n+1).
In conclusion, ϴ is not quite as strong as your statement would have it, but it is analogous, which probably caused your confusion. What it does imply is that both f(n) = O(g(n)) and f(n) = Ω(g(n)).
The answer above is right, but I wanted to provide answer that goes into the "why" from a different perspective.
Firstly, f(n) = ϴ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).
You probably also know that f(n) = O(g(n)) if and only if f(n) ≤ c ⋅ g(n) for all n ≥ n0 and some c > 0. In plain English, that roughly means that "eventually, f(n) is always smaller or equal to g(n) scaled by some constant".
Similarly, we also know that f(n) = Ω(g(n)) if and only if f(n) ≥ d ⋅ g(n) for all n ≥ n0 and some d > 0. The plain English translation of this is that we know "eventually, f(n) is always smaller or equal to g(n) scaled by some constant".
Since f(n) = ϴ(g(n)), you know that both of the plain English statements must be true and should be able to see pretty clearly that no where in those two statements is there any guarantee that f(n) = c ⋅ g(n) for all n ≥ n0.
Related