Tell me more ×
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.
up vote 2 down vote favorite

I'm trying to find the largest $g(n)$ such that $\lim_{n\rightarrow\infty} \frac{g^4(n)}{n-g(n)}=0$. It doesn't seem to be sufficient if $g(n) = o(n^{1/4})$. Any hints?

share|improve this question
3  
How does one choose the largest? If I were to choose any function in $O(n^{1/4 - \epsilon})$ for any $\epsilon > 0$, the limit would be $0$ for example. – mixedmath♦ Aug 3 '12 at 4:33
Ah thanks, I missed that the limit indeed goes to 0 if $g(n) \in o(n^{1/4})$. – somebody Aug 3 '12 at 4:44

closed as not a real question by Did, William, Thomas, BenjaLim, J. M. Sep 27 '12 at 10:29

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

1 Answer

up vote 2 down vote accepted

Just to have an answer here: I interpret "the largest $g$" as a (less vague) statatement "weakest possible condition on $g$". In which case the answer is: the weakest possible condition is $g = o(n^{1/4})$. Indeed, $g = o(n^{1/4})\implies g^4=o(n) \implies n=O(n-g^4)$, and we end up with $g^4/(n-g(n))=o(1)$.

The condition cannot be weakened to $O(n^{1/4})$, as the example $g(n)=n^{1/4}$ shows.

share|improve this answer

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