# Asymptotic time complexity

1. Aug 8, 2014

### Maylis

1. The problem statement, all variables and given/known data
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$?

2. Relevant equations

3. 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).

2. Aug 8, 2014

### .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.

3. Aug 8, 2014

### Maylis

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

Last edited: Aug 8, 2014
4. Aug 9, 2014

### .Scott

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.

5. Aug 9, 2014

### Maylis

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$?

6. Aug 9, 2014

### .Scott

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

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted