World's most popular travel blog for travel bloggers.

# How can time complexities be elements of others?

, ,
Problem Detail:

I have a problem that I solved, but I'm unsure if my answers are correct or not. I've never seen the implementation of time complexities as elements of others.

f(n) element of O(log(n)) g(n) element of theta(n) 

Prove if the below are true are false, provide a counter example if it's false.

1) g(n) element of omega(f(n)) 2) f(n)g(n) element of O(nlog(n)) 3) f(n)g(n) element of theta(nlog(n)) 

Below are my attempts, which was just because I thought it was the logical solution. Any ideas on how I can go about solving these types of questions?

1) False, g(n) has a tight bound at (n). If it had a lower bound of f(n), then g(n) should allow log(n), but that's too high of a complexity.

2) True

3) False, f(n) having an upper bound of log(n) implies it could be even faster. Setting a tight bound contradicts that wherein it cant go faster.

###### Asked By : Andrew Raleigh

Actually the 1) is true: omega means "at least", and $O$ means "at most". You now that $g(n)$ is in $n$, which is at least $\log(n)$.

2) is indeed true

For 3) you don't have enough information: it is only true if $f$ is in $\theta(log (n))$ which you don't know, so 3) could be true or false. You can give a counter example where it is false: $f(n)=\log(\log (n)))$ and $g(n)=n$.

Question Source : http://cs.stackexchange.com/questions/57970

3200 people like this