2
$\begingroup$

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.

  • 0
    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.2011-09-18

3 Answers 3

3

$\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}$

1

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.

  • 0
    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.2011-09-18
0

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})}$.

  • 0
    Thanks for the answer, had to go with first submission for check mark though.2011-09-18