Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

[THIS IS HOMEWORK so please, don't just provide solutions, help me reasoning]

I'm dealing with the following problem:
Let $f(n)$ be the worst case time complexity of an algorithm A. Assume that there exist $c > 0$ and $n_{0}$, such that for each $n > n_{0}$ there exists an input of size $n$ for which A runs in exactly $c\cdot{g(n)}$ steps.

a. Is it necessarily true that $f(n) = \Omega(g(n))$?
b. Assume $f(n) = O(g(n))$. Is it necessarily true that $f(n) = \Theta(g(n))$?


For a. I think it must be true since the $\Omega$ notation has on it all the elements that are either $f(n) = c\cdot g(n)$ or $f(n) > c\cdot g(n)$ so following the assumption leads to $f(n) = c\cdot g(n)$ being always true, therefore making the whole sentence true. (hope I'm right).
For b. I assume $f(n) = O(g(n))$ and $f(n)=c\cdot{g(n)}$ ($\forall{n>n_{0}}$... of course) then I concluded that since (a) is true then $f(n) = \Theta(g(n))$.

any help will be appreciated, thanks.

share|improve this question
    
Part b. seems a little strange. If you're already given that $f(n) = c\,g(n)$ when $n$ is large enough why do you need to assume that $f(n) = O(g(n))$? Is that exactly how the question was written? –  Antonio Vargas Apr 15 '12 at 13:15
    
@Antonio yes by 100% –  JanosAudron Apr 15 '12 at 13:27
1  
In that case then I think your reasoning is correct. Everything is easy if you know that $f(n) = c \,g(n)$ eventually. –  Antonio Vargas Apr 15 '12 at 14:07
add comment

1 Answer

The reasoning for $f(n)=c\,g(n)$ is not correct; this equality need not hold under the stated assumptions.

In mathematical terms, the assumption

Assume that there exist $c>0$ and $n_0$, such that for each $n>n_0$ there exists an input of size $n$ for which $A$ runs in exactly $c\,g(n)$ steps.

becomes $$f(n)\ge cg(n)\quad \text{when }\ n>n_0 \tag1$$ because $f$ is the maximal running time among all inputs of size $n$. We cannot conclude that equality holds in (1) because nothing excludes the possibility that an input exists that runs in more than $c\,g(n)$ steps.

a) Yes, compare (1) to the definition of $\Omega$.

b) Yes, $\Theta$ means "$O$ and $\Omega$".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.