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.

I have two functions, $f(n)$ and $g(n)$, and I am trying to determine whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$. I am not sure about my answers. Help will be appreciated.

a) $f(n)=n + \log(\log^2n)$, $g(n)=100n + (\log(n))^2$. I believe here, $f(n)$ is $\Theta(g(n))$ because we can ignore the lower order terms in $f(n)$ and $g(n)$, and so we are left with $f(n)=n$, $g(n)=100n$, and so $f(n)=\Theta(g(n))$.

b) $f(n)=3n(\log(n!)) + n^2$, $g(n)= n^2\log(\log(n))$. I think here $f(n)$ is $O(g(n)$ because $g(n)$ dominates all the time because of the term $n^2\log(\log n)$.

Am i right in my answers? Thanks for the help.

share|improve this question
1  
For (b), do you know about Stirling's formula? The log of $n!$ is about $nlog n$, more precisely about $n(\log n-e)$, so for large $n$ we get that $g(n)\lt f(n)$. Thus $g(n)$ is $O(f(n))$. –  André Nicolas Feb 25 '13 at 7:44
    
g(n) is O(f(n)) or f(n) is O(g(n))? –  bigO Feb 25 '13 at 7:48
    
The first. In the long run, and I think not that long, $g(n)$ is smaller than $f(n)$. The ratio $g(n)/f(n)$ in fact approaches $0$, so $f(n)$ is not $O(g(n))$. –  André Nicolas Feb 25 '13 at 7:53
    
I see now, thanks –  bigO Feb 25 '13 at 7:54

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.