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've placed this on the Math Stack Exchange even though it is really a CS question because it is the math that is stumping me.

Please note, I'm not asking you to do this problem for me, just to make sure I'm not wasting my life on an impossible problem

For the function $t(n)=\sqrt{10n^2 + 7n + 3}$, indicate the class $\Theta(g(n))$ that the function belongs to. (Use the simplest $g(n)$ possible in your answers.) Prove your assertions.

For $ n\ge 1$, this function exhibits linear growth and can be bounded by functions $c_2 g(n)=1n$ and $c_1 g(n)=5n$, so it belongs to $\Theta(n)$. I've checked my intuition on this computationally and I am satisfied that this is the case.

My problem is that I cannot justify this. I've tried factoring the polynomial portion without any luck (no real roots, apparently?). When I try to set up $\lim_{n\to\infty} \frac{t(n)}{g(n)}$, I find I can neither simplify it nor achieve an answer via repeated applications of L'Hopital's Rule. I am at wits' end here. Am I missing something, or does this problem belong on the errata page for the textbook in question?

PS: Textbook in question is Introduction to Design and Analysis of Algorithms, 2nd Edition by Anany Levitin. This is problem 2.2.3. My google-fu has not yielded the errata page for this textbook.

share|improve this question
    
Thank you for the clean-up edit. –  chucksmash Sep 18 '11 at 2:34
    
Make it clear that you are trying to find how efficient your most expensive operation is within in one or more coding loops. C(n) is running time, and g(n) will be the equation upon which C(n) rests... Ie... g(n) n^(infinity power) it will take a long time to run. –  RetroCoder Sep 18 '11 at 10:09
add comment

3 Answers

up vote 4 down vote accepted

$$\frac{\sqrt{10n^2+7n+3}}{n} = \frac{\sqrt{10n^2+7n+3}}{\sqrt{n^2}} = \sqrt{\frac{10n^2+7n+3}{n^2}} = \sqrt{10+7/n+3/n^2}$$

share|improve this answer
add comment

If you extend $t(n)$ to a function of the nonnegative real numbers, you can use calculus to find the maximum value of $t(n)/5n$. Set the derivative of this to 0 to find critical points and then demonstrate that after a certain point, the function is decreasing (and hence bounded).

Alternatively, if you want to use your method of factoring, the fact that the square root function is increasing means you can replace $10n^2+7n+3$ with a polynomial which is always larger for positive $n$, but is easy to factor.

edit: forgot to mention that lower bounds can be established with very similar methods.

share|improve this answer
    
computer lagged when I posted, and so I got ninja'd. I'll leave this here because it's a different way to do it than the others mentioned. –  Logan Maingi Sep 18 '11 at 2:37
add comment

We have $t(n)=\sqrt{10n^2 + 7n + 3}$. Perhaps you should consider writing it as $t(n) = \sqrt{n^2( 10 + \frac{7}{n} + \frac{3}{n^2})} = n \sqrt{( 10 + \frac{7}{n} + \frac{3}{n^2})}$.

share|improve this answer
    
Thanks for the answer, had to go with first submission for check mark though. –  chucksmash Sep 18 '11 at 2:42
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.