MHB Finding the asymptotic complexity of a function

[evinda]

Hello! (Wave)

I want to find the asymptotic complexity of the function:

$$g(n)=n^6-4n^5 \log^2 n-10-5n^3$$

 

[evinda]

Could we do it like that? (Thinking)

$$g(n)=n^6-4n^5 \log^2 n -10-5n^3 \geq n^6-\frac{4}{10}n^6-\frac{10}{64}n^6-\frac{5}{27}n^6=\left ( 1-\frac{4}{10}-\frac{10}{64}-\frac{5}{27} \right ) n^6=\frac{1117}{4320}n^6$$

If so, how can we find a $n_0$, so that the inequality stands? (Thinking)

 

[I like Serena]

Hello! (Wave)

I want to find the asymptotic complexity of the function:

$$g(n)=n^6-4n^5 \log^2 n-10-5n^3$$

Could we do it like that? (Thinking)

$$g(n)=n^6-4n^5 \log^2 n -10-5n^3 \geq n^6-\frac{4}{10}n^6-\frac{10}{64}n^6-\frac{5}{27}n^6=\left ( 1-\frac{4}{10}-\frac{10}{64}-\frac{5}{27} \right ) n^6=\frac{1117}{4320}n^6$$

If so, how can we find a $n_0$, so that the inequality stands? (Thinking)

What do you think is the dominant term? (Wondering)If you have an idea about that, let's call that $d(n)$.

Then, to verify if you have it right, you can use the equivalent definition that:
$$g(n)=\Theta(d(n)) \iff \exists L > 0 \text{ such that }\limsup_{n\to \infty}\left| \frac{g(n)}{d(n)} \right| = L$$

 

[evinda]

What do you think is the dominant term? (Wondering)If you have an idea about that, let's call that $d(n)$.

Then, to verify if you have it right, you can use the equivalent definition that:
$$g(n)=\Theta(d(n)) \iff \exists L > 0 \text{ such that }\limsup_{n\to \infty}\left| \frac{g(n)}{d(n)} \right| = L$$

Isn't the dominant term in this case $n^6$ ? (Thinking)

Is the way I did it, at my last post, wrong?

 

[I like Serena]

Isn't the dominant term in this case $n^6$ ? (Thinking)

Yes.
But how do you know that it isn't $4n^5\log^2 n$? (Wondering)

Is the way I did it, at my last post, wrong?

It's right.
But it's not enough for asymptotic equality yet. (Wasntme)

 

[evinda]

Yes.
But how do you know that it isn't $4n^5\log^2 n$? (Wondering)

I thought so, since:

$$\lim_{n \to \infty} \frac{n^6}{4n^5 \log^2 n}=\lim_{n \to +\infty} \frac{n}{4 \log^2 n}=\lim_{n \to +\infty} \frac{1}{\frac{8 \log n}{n}}=\lim_{n \to +\infty} \frac{n}{8 \log n}=\lim_{n \to +\infty} \frac{1}{\frac{8}{n}}=\lim_{n \to +\infty} \frac{n}{8}=+\infty$$

Can we not conclude it from that? (Thinking)

It's right.
But it's not enough for asymptotic equality yet. (Wasntme)

What else could we do? (Thinking)

 

[I like Serena]

I thought so, since:

$$\lim_{n \to \infty} \frac{n^6}{4n^5 \log^2 n}=\lim_{n \to +\infty} \frac{n}{4 \log^2 n}=\lim_{n \to +\infty} \frac{1}{\frac{8 \log n}{n}}=\lim_{n \to +\infty} \frac{n}{8 \log n}=\lim_{n \to +\infty} \frac{1}{\frac{8}{n}}=\lim_{n \to +\infty} \frac{n}{8}=+\infty$$

Can we not conclude it from that? (Thinking)

Yes. Yes, we can. (Nod)

What else could we do? (Thinking)

Effectively you have proven that $g(n) = \Omega(n^6)$.

Don't you need $g(n) = \Theta(n^6)$? (Wondering)

 

[evinda]

Effectively you have proven that $g(n) = \Omega(n^6)$.

But.. what $n_1$ can we take? (Worried)

Don't you need $g(n) = \Theta(n^6)$? (Wondering)

It is $g(n)=n^6-4n^5 \log^2 n-10-5n^3 \leq n^6, \forall n \geq 1$.

So, we can pick $n_2=1$ and $c_2=1$, and we have that $g(n)=O(n^6)$, right? (Thinking)

 

[I like Serena]

But.. what $n_1$ can we take? (Worried)

Won't $n_1=1$ do just fine? (Wondering)

It is $g(n)=n^6-4n^5 \log^2 n-10-5n^3 \leq n^6, \forall n \geq 1$.

So, we can pick $n_2=1$ and $c_2=1$, and we have that $g(n)=O(n^6)$, right? (Thinking)

Yep. (Smirk)

 

[evinda]

Won't $n_1=1$ do just fine? (Wondering)

But.. it doesn't stand $\forall n \geq 1$, or am I wrong? (Worried)

Shouldn't we pick a greater $n_1$? (Thinking)

 

[I like Serena]

But.. it doesn't stand $\forall n \geq 1$, or am I wrong? (Worried)

Shouldn't we pick a greater $n_1$? (Thinking)

Oh right. (Blush)Well, you had just found this limit:

$$\lim_{n \to \infty} \frac{n^6}{4n^5 \log^2 n}=\lim_{n \to +\infty} \frac{n}{4 \log^2 n}=\lim_{n \to +\infty} \frac{1}{\frac{8 \log n}{n}}=\lim_{n \to +\infty} \frac{n}{8 \log n}=\lim_{n \to +\infty} \frac{1}{\frac{8}{n}}=\lim_{n \to +\infty} \frac{n}{8}=+\infty$$

Let's invert the fraction.
Then we have:
$$\lim_{n \to \infty} \frac{4n^5 \log^2 n}{n^6} = 0$$

This means that:
$$\forall\, \varepsilon > 0 \ \exists\, n_0 \text{ such that }\forall\, n>n_0: \left| \frac{4n^5 \log^2 n}{n^6} \right| < \varepsilon$$

If we pick $\varepsilon=\frac{4}{10}$, we get that there is an $n_0$ such that for each $n > n_0$:
$$4n^5 \log^2 n < \frac{4}{10}n^6$$

So we don't have a specific value for this $n_0$, but we do know that it exists.
That is enough for what you want to proof. (Mmm)How could you apply this reasoning to the whole expression? (Wondering)

 

[evinda]

Well, you had just found this limit:

Let's invert the fraction.
Then we have:
$$\lim_{n \to \infty} \frac{4n^5 \log^2 n}{n^6} = 0$$

This means that:
$$\forall\, \varepsilon > 0 \ \exists\, n_0 \text{ such that }\forall\, n>n_0: \left| \frac{4n^5 \log^2 n}{n^6} \right| < \varepsilon$$

If we pick $\varepsilon=\frac{4}{10}$, we get that there is an $n_0$ such that for each $n > n_0$:
$$4n^5 \log^2 n < \frac{4}{10}n^6$$

So we don't have a specific value for this $n_0$, but we do know that it exists.
That is enough for what you want to proof. (Mmm)How could you apply this reasoning to the whole expression? (Wondering)

So, could we do it like that? (Thinking)

$$\lim_{n \to \infty} \frac{4n^5 \log^2 n}{n^6} = 0$$

This means that:
$$\forall\, \varepsilon > 0 \ \exists\, n_0 \text{ such that }\forall\, n>n_0: \left| \frac{4n^5 \log^2 n}{n^6} \right| < \varepsilon$$

If we pick $\varepsilon=\frac{4}{10}$, we get that there is an $n_0$ such that for each $n > n_0$:
$$4n^5 \log^2 n < \frac{4}{10}n^6$$

So, we have:

$$g(n)=n^6-4n^5 \log^2 n -10-5n^3 \geq n^6-\frac{4}{10}n^6-\frac{10}{64}n^6-\frac{5}{27}n^6=\left ( 1-\frac{4}{10}-\frac{10}{64}-\frac{5}{27} \right ) n^6=\frac{1117}{4320}n^6, \forall n \geq \max \{ \lfloor n_0 \rfloor+1,3 \}$$

So, we pick $n_1= \max \{ \lfloor n_0 \rfloor+1,3 \}, c_1=\frac{1117}{4320}$.
$$g(n)=n^6-4n^5 \log^2 n-10-5n^3 \leq n^6, \forall n \geq 1$$

So, we pick $n_2=1, c_2=1$

Now, we pick $n_0=\max \{ \max \{ \lfloor n_0 \rfloor+1,3 \} \}, c_1=\frac{1117}{4320}$ and $c_2=1$ and we have that:
$$g(n)=\Theta(n^6)$$

Or is it better like that? (Wasntme)

$$\lim_{n \to \infty} \frac{4n^5 \log^2 n}{n^6} = 0$$

This means that:
$$\forall\, \varepsilon > 0 \ \exists\, n_1 \text{ such that }\forall\, n>n_1: \left| \frac{4n^5 \log^2 n}{n^6} \right| < \varepsilon$$

If we pick $\varepsilon=\frac{4}{10}$, we get that there is an $n_1$ such that for each $n > n_1$:
$$4n^5 \log^2 n < \frac{4}{10}n^6$$$$\lim_{n \to +\infty} \frac{10}{n^6}=0$$

This means that:
$$\forall\, \varepsilon > 0 \ \exists\, n_0 \text{ such that }\forall\, n>n_2: \left| \frac{10}{n^6} \right| < \varepsilon$$

If we pick $\varepsilon=\frac{10}{64}$, we get that there is an $n_2$ such that for each $n > n_2$:
$$10 < \frac{10}{64}n^6$$

$$\lim_{n \to +\infty} \frac{5n^3}{n^6}=0$$

This means that:
$$\forall\, \varepsilon > 0 \ \exists\, n_3 \text{ such that }\forall\, n>n_3: \left| \frac{5n^3}{n^6} \right| < \varepsilon$$

If we pick $\varepsilon=\frac{5}{27}$, we get that there is an $n_3$ such that for each $n > n_3$:
$$5n^3 < \frac{5}{27}n^6$$

So, we have:

$$g(n)=n^6-4n^5 \log^2 n -10-5n^3 \geq n^6-\frac{4}{10}n^6-\frac{10}{64}n^6-\frac{5}{27}n^6=\left ( 1-\frac{4}{10}-\frac{10}{64}-\frac{5}{27} \right ) n^6=\frac{1117}{4320}n^6, \forall n \geq \max \{ n_1,n_2,n_3\}$$

So, we pick $n_4=\max \{ n_1,n_2,n_3\}, c_1=\frac{1117}{4320}$.
$$g(n)=n^6-4n^5 \log^2 n-10-5n^3 \leq n^6, \forall n \geq 1$$

So, we pick $n_5=1, c_2=1$

Now, we pick $n_0=\max \{ 1, \max \{ n_1,n_2,n_3\} \}, c_1=\frac{1117}{4320}$ and $c_2=1$ and we have that:
$$g(n)=\Theta(n^6)$$

(Thinking)

 

[I like Serena]

That all looks correct! (Nod)
I think you can do it both ways.But... what if we take a look at:
$$\lim_{n\to\infty} \frac{g(n)}{n^6} = \lim_{n\to\infty} \frac{n^6-4n^5 \log^2 n-10-5n^3}{n^6}$$

What is the value of this limit? (Wondering)

And what does it mean? (Wondering)

 

[evinda]

That all looks correct! (Nod)
I think you can do it both ways.

A ok! (Nod)

But... what if we take a look at:
$$\lim_{n\to\infty} \frac{g(n)}{n^6} = \lim_{n\to\infty} \frac{n^6-4n^5 \log^2 n-10-5n^3}{n^6}$$

What is the value of this limit? (Wondering)

$$\lim_{n\to\infty} \frac{g(n)}{n^6} = \lim_{n\to\infty} \frac{n^6-4n^5 \log^2 n-10-5n^3}{n^6}=\lim_{n \to \infty} \left ( 1-\frac{4 \log^2 n}{n}-\frac{10}{n^6}-\frac{5}{n^3}\right) =(*)$$

Since:

$$\lim_{n \to \infty} \frac{\log^2 n}{n}\overset{\text{DLH}}{=} \lim_{n \to \infty}\frac{2 \log n}{n} \overset{\text{DLH}}{=} \lim_{n \to \infty} \frac{2}{n}=0$$

$$(*)=1$$

And what does it mean? (Wondering)

I don't know.. (Sweating) What could this mean? (Thinking)

 

[I like Serena]

$$\lim_{n\to\infty} \frac{g(n)}{n^6} = \lim_{n\to\infty} \frac{n^6-4n^5 \log^2 n-10-5n^3}{n^6}=\lim_{n \to \infty} \left ( 1-\frac{4 \log^2 n}{n}-\frac{10}{n^6}-\frac{5}{n^3}\right) =(*)$$

Since:

$$\lim_{n \to \infty} \frac{\log^2 n}{n}\overset{\text{DLH}}{=} \lim_{n \to \infty}\frac{2 \log n}{n} \overset{\text{DLH}}{=} \lim_{n \to \infty} \frac{2}{n}=0$$

$$(*)=1$$

Good! (Nod)

I don't know.. (Sweating) What could this mean? (Thinking)

What does this limit mean according to the definition of a limit ($\varepsilon$-style)? (Wondering)

 

[evinda]

What does this limit mean according to the definition of a limit ($\varepsilon$-style)? (Wondering)

$$\lim_{n \to \infty} \frac{g(n)}{n^6}=1 $$That means that $\forall \epsilon>0, \exists n_0$ such that $\forall n > n_0:$

$$|\frac{g(n)}{n^6}-1|< \epsilon$$

Right? (Thinking) What can we conclude from that?

 

[I like Serena]

$$\lim_{n \to \infty} \frac{g(n)}{n^6}=1 $$

That means that $\forall \epsilon>0, \exists n_0$ such that $\forall n > n_0:$

$$|\frac{g(n)}{n^6}-1|< \epsilon$$

Right? (Thinking) What can we conclude from that?

That:
$$1 - \epsilon< \frac{g(n)}{n^6}< 1 + \epsilon$$
$$(1 - \epsilon)n^6< g(n)< (1 + \epsilon)n^6$$

Recognize it? (Wondering)

 

[evinda]

That:
$$1 - \epsilon< \frac{g(n)}{n^6}< 1 + \epsilon$$
$$(1 - \epsilon)n^6< g(n)< (1 + \epsilon)n^6$$

Recognize it? (Wondering)

So could we just take $c_1=1-\epsilon$, $c_2=1+\epsilon$ , using the definition of the limit $\lim_{n \to \infty} \frac{g(n)}{n^6}$? (Thinking)

 

[I like Serena]

So could we just take $c_1=1-\epsilon$, $c_2=1+\epsilon$ , using the definition of the limit $\lim_{n \to \infty} \frac{g(n)}{n^6}$? (Thinking)

Yes! (Party)

 

[evinda]

Oh right. (Blush)Well, you had just found this limit:Let's invert the fraction.
Then we have:
$$\lim_{n \to \infty} \frac{4n^5 \log^2 n}{n^6} = 0$$

This means that:
$$\forall\, \varepsilon > 0 \ \exists\, n_0 \text{ such that }\forall\, n>n_0: \left| \frac{4n^5 \log^2 n}{n^6} \right| < \varepsilon$$

If we pick $\varepsilon=\frac{4}{10}$, we get that there is an $n_0$ such that for each $n > n_0$:
$$4n^5 \log^2 n < \frac{4}{10}n^6$$

So we don't have a specific value for this $n_0$, but we do know that it exists.
That is enough for what you want to proof. (Mmm)How could you apply this reasoning to the whole expression? (Wondering)

If $n^6$ would have a coefficient $a_1 \neq 1$, would we use it at the limit and therefore at the definition? (Thinking)

$\lim_{n \to \infty} \frac{4n^5 \log^2 n}{a_1 n^6} = 0$

Or wouln't we have to use it?

 

[evinda]

That:
$$1 - \epsilon< \frac{g(n)}{n^6}< 1 + \epsilon$$
$$(1 - \epsilon)n^6< g(n)< (1 + \epsilon)n^6$$

Recognize it? (Wondering)

$$g(n)=\Theta(n^6)$$

means that $\exists c_1,c_2>0$ and $n_0 \geq 0$ such that $\forall n \geq n_0$:

$$c_1 \cdot n^6 \leq g(n) \leq c_2 n^6$$

By taking $c_1=1-\epsilon$, $c_2=1+\epsilon$, we don't have $ \leq$ and $\geq$, but $<$ and $>$.
Is it a problem? (Thinking)

 

[I like Serena]

$$g(n)=\Theta(n^6)$$

means that $\exists c_1,c_2>0$ and $n_0 \geq 0$ such that $\forall n \geq n_0$:

$$c_1 \cdot n^6 \leq g(n) \leq c_2 n^6$$

By taking $c_1=1-\epsilon$, $c_2=1+\epsilon$, we don't have $ \leq$ and $\geq$, but $<$ and $>$.
Is it a problem? (Thinking)

No problem. (Wasntme)

Note that:
$$(1-\epsilon) \cdot n^6 < g(n) < (1+\epsilon) n^6 \quad\Rightarrow \quad
(1-\epsilon) \cdot n^6 \leq g(n) \leq (1+\epsilon) n^6$$

We should still pick a value for $\epsilon$ though. (Nerd)

 

[evinda]

No problem. (Wasntme)

Note that:
$$(1-\epsilon) \cdot n^6 < g(n) < (1+\epsilon) n^6 \quad\Rightarrow \quad
(1-\epsilon) \cdot n^6 \leq g(n) \leq (1+\epsilon) n^6$$

I understand! (Nod)

We should still pick a value for $\epsilon$ though. (Nerd)

We can pick what $0<\epsilon<1$ we want, right? (Thinking)

So, we could pick, for example , $\epsilon=\frac{3}{4}$, right? (Thinking)

 

[I like Serena]

We can pick what $0<\epsilon<1$ we want, right? (Thinking)

So, we could pick, for example , $\epsilon=\frac{3}{4}$, right? (Thinking)

Exactly! (Nod)

 

[evinda]

Exactly! (Nod)

I understand! (Nod) Thanks a lot! (Clapping)