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'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

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, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

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
add comment

1 Answer 1

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
add comment

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