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.

Find an example of a function $f$ such that satisfies: $$\forall_{\varepsilon>0} \ f(n)=O(n^{1+\varepsilon})$$ but not $$f(n)=O(n)$$

I had been thinking about it for an hour and still can't find it. Can anybody help?

share|improve this question
    
Try multiplying two functions from different "growth classes". –  Antonio Vargas Dec 2 '12 at 15:16
    
Related: can you find a function which is $O(n^{\varepsilon})$ for all positive $\varepsilon$ but is not $O(1)$? –  WimC Dec 2 '12 at 15:22
    
I was trying to approach this way, but failed. –  xan Dec 2 '12 at 15:26
    
Well, what were you trying? –  Antonio Vargas Dec 2 '12 at 15:30
    
Like WimC said I was trying to approach. For example $n^{1/n}=O(n^{\varepsilon})$ for every $\varepsilon$, unfortunately it's also $O(1)$. –  xan Dec 2 '12 at 15:33
add comment

1 Answer 1

up vote 1 down vote accepted

Hint: $\log n = O(n^{\epsilon})$ for all $\epsilon > 0$.

share|improve this answer
    
Try to prove it, if necessary :) –  Antonio Vargas Dec 2 '12 at 15:39
    
I can see now, the answer is $f(n)=n^{1+\log n}$ it was simpler than I thought. –  xan Dec 2 '12 at 15:40
    
@xan, that function is not $O(n^{1+\epsilon})$ for all $\epsilon > 0$. –  Antonio Vargas Dec 2 '12 at 15:44
    
$n\log n$ the solution is –  xan Dec 2 '12 at 15:54
    
@xan, there you go :) –  Antonio Vargas Dec 2 '12 at 15:54
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.