What Determines the Asymptotic Time Complexity of T(n)=n^2+3?

[gfd43tg]

Homework Statement

In this question you will determine the asymptotic time complexity of an algorithm for which the complexity is $T(n)=n^{2}+3$.

Find a positive real c and a positive integer $k$, such that

$T(n) \le cf(n)$

holds for all $n>k$ if $f(n)$ is the asymptotic time complexity.

What is the best choice for $f(n)$?

[ans]

What is a good choice for $c$ such that $k$ is small (i.e. less than 10)?What is $k$?

Homework Equations

The Attempt at a Solution

I am confused how to approach these problems. Unfortunately the choices for $f(n)$ are not visible, there is a bug in the problem. But I was wondering what I should do in order to do these problems. The notes are not adequate (or available to look at, since that is bugged as well).

 

[.Scott]

If there was a specific list of $f(n)$'s that you don't have, then you're left guessing.
Commonly, the $f(n)$ is pretty simple, such as $f(n) = e^n$, $n^3$, or $n^2$.

Among those choices, $f(n) = n^2$ would be best. Then use a c of 1.5 and a k of 3.

 

[gfd43tg]

You mean there is no way to analytically choose it?

The bug has been fixed, so the choices are
$n^2$, $n$, $nlog(n)$, and $n^3$, so I pick $n^2$ since that is the closest to $n^2 + 3$. Next, for $k$ being small (less than 10), I just do $k = 9$ and all $n \gt 9$.

The choices for $c$ are 5, 0.5, 2, and 1, so I pick 2 since the inequality $n^2 + 3 \le 2n^2$ will be true for all $n > 9$.

Next they ask what $k$ is, and the choices are 1, 10, 2, and 5. Well, what the heck do I do for that??

 

[.Scott]

You mean there is no way to analytically choose it?

The bug has been fixed, so the choices are
$n^2$, $n$, $nlog(n)$, and $n^3$, so I pick $n^2$ since that is the closest to $n^2 + 3$. Next, for $k$ being small (less than 10), I just do $k = 9$ and all $n \gt 9$.

The choices for $c$ are 5, 0.5, 2, and 1, so I pick 2 since the inequality $n^2 + 3 \le 2n^2$ will be true for all $n > 9$.

Next they ask what $k$ is, and the choices are 1, 10, 2, and 5. Well, what the heck do I do for that??

Hey, I didn't do too bad at picking an $f(n)$ and $c$ without knowing the choices! Did I?

They want $T(n)≤cf(n)$ for all $n>k$.
with $T(n)=n^2+3$ and $cf(n)=2(n^2)$.
So, we have $n^2+3 <= 2n^2$ for all $n>k$.

Clearly, if $n=0$, then $0^2+3 <= 2(0^2)$, so $3<=0$, which is false. So $n=0$ doesn't work.

Let me know if you can't take it from there - I'll walk you through the rest.

 

[gfd43tg]

The problem I have with this is that when you pick $c$, it's almost as if you are simultaneously supposing a $k$. Are you supposed to pick the $c$ without regards to a possible $k$?

 

[.Scott]

The problem I have with this is that when you pick $c$, it's almost as if you are simultaneously supposing a $k$.

What you should notice is that as long as $c$ is greater than 1, there will be a $k$. If $c$ is one or less, then $T(N)$ will always be greater than $cf(n)$. So, without a list to choose from, I picked $c=1.5$ which would have required $n>2 (k=2)$. Notice that in this case, even a $c$ that is slightly above 1, allows k to be fairly small.

Are you supposed to pick the $c$ without regards to a possible $k$?

This is pretty much just an academic exercise. For most real applications, it would be good enough to say that it was approximates $cn^2$ without worrying about the exact value of $c$.