MHB Why can we not apply the theorem?

[evinda]

Hi! (Wave)

Find an exact asymptotic solution of the recurrence relation $T(n)=4T \left ( \frac{n}{2}\right )+n^2 \log_2{(\log_2 n)}$, using the master theorem or show that the master theorem cannot be applied.

In this case, the master theorem cannot be applied, right? (Thinking)

But, how could we show it? (Thinking)

 

[I like Serena]

Hi! (Wave)

Find an exact asymptotic solution of the recurrence relation $T(n)=4T \left ( \frac{n}{2}\right )+n^2 \log_2{(\log_2 n)}$, using the master theorem or show that the master theorem cannot be applied.

In this case, the master theorem cannot be applied, right? (Thinking)

But, how could we show it? (Thinking)

Hey! (Smile)

How about showing that the preconditions of each of the possible cases are not satisfied? (Thinking)

 

[evinda]

Hey! (Smile)

How about showing that the preconditions of each of the possible cases are not satisfied? (Thinking)

So, do I have to show that none of these relations stand? (Thinking)

• $f(n)=O(n^{\log_b a- \epsilon})$
• $f(n)=\Theta(n^{\log_b a})$
• $f(n)=\Omega(n^{\log_b a+ \epsilon}) \text{ and } \exists c<1 \text{ such that: } a f \left ( \frac{n}{b}\right ) \leq c f(n)$

 

[evinda]

If so, how could I do this? (Thinking)

 

[I like Serena]

So, do I have to show that none of these relations stand? (Thinking)

• $f(n)=O(n^{\log_b a- \epsilon})$
• $f(n_=\Theta(n^{\log_b a})$
• $f(n)=\Omega(n^{\log_b a+ \epsilon}) \text{ and } \exists c<1 \text{ such that: } a f \left ( \frac{n}{b}\right ) \leq c f(n)$

That looks about right, although I think the second should be:
$$f(n)=\Theta(n^{\log_b a} \log^k n)\text{ with }k \ge 0$$

If so, how could I do this? (Thinking)

Let's start with the first.
We know that $\log_b a=\log_2 4 = 2$.
Since $f(n)=\Theta(n^2\log_2(\log_2 n))$, it follows that $f(n)\ne O(n^c)$ with $c < 2$.

 

[evinda]

That looks about right, although I think the second should be:
$$f(n)=\Theta(n^{\log_b a} \log^k n)\text{ with }k \ge 0$$

Isn't it $f(n)=n^{\log_b a}$, from which it follows that $T(n)=\Theta(n^{\log_b a} \lg n)$ ? (Thinking)

Let's start with the first.
We know that $\log_b a=\log_2 4 = 2$.
Since $f(n)=\Theta(n^2\log_2(\log_2 n))$, it follows that $f(n)\ne O(n^c)$ with $c < 2$.

So, can we just say that it follows that $f(n)\ne O(n^c)$ with $c < 2$, or do we have to explain it further? (Thinking)

 

[I like Serena]

Isn't it $f(n)=n^{\log_b a}$, from which it follows that $T(n)=\Theta(n^{\log_b a} \lg n)$ ? (Thinking)

For what it is worth, wikipedia gives a more general second case.

So, can we just say that it follows that $f(n)\ne O(n^c)$ with $c < 2$, or do we have to explain it further? (Thinking)

I believe so.
It is possible to prove it explicitly, but I consider that overdone. (Wasntme)

 

[evinda]

For what it is worth, wikipedia gives a more general second case.

In my notes, at the the second case, it is $f(n)=\Theta(n^{\log_b a})$.. (Wasntme)

I believe so.
It is possible to prove it explicitly, but I consider that overdone. (Wasntme)

So, in order to reject the second case, could we say it like that? (Thinking)

Since $f(n)=\Theta(n^2 \log_2{ \log_2 n})$, it follows that
$f(n) \neq \Theta(n^2)$.

Also, what could we say about the third case?

How could we prove it explicitly? (Thinking)

 

[I like Serena]

So, in order to reject the second case, could we say it like that? (Thinking)

Since $f(n)=\Theta(n^2 \log_2{ \log_2 n})$, it follows that
$f(n) \neq \Theta(n^2)$.

Actually, we can phrase it slightly sharper and say:

Since $f(n)=n^2 \log_2{ \log_2 n}$, it follows that $f(n) \neq \Theta(n^2)$. (Nerd)

How could we prove it explicitly? (Thinking)

Suppose $n^2\log_2(\log_2 n) = O(n^c)$ with $c<2$.

Then that means that $\exists M >0, \exists n_0$ such that $\forall n \ge n_0$: $n^2\log_2(\log_2 n) < Mn^2$.
This implies $\forall n \ge n_0: \log_2(\log_2 n) < M$, which is a contradiction.

Therefore $n^2\log_2(\log_2 n) \ne O(n^c)$ with $c<2$. (Coffee)

Also, what could we say about the third case?

Give it a try? (Thinking)

 

[evinda]

Actually, we can phrase it slightly sharper and say:

Since $f(n)=n^2 \log_2{ \log_2 n}$, it follows that $f(n) \neq \Theta(n^2)$. (Nerd)

And could we prove it like that? (Thinking)

We suppose that $f(n)=\Theta(n^2)$.

Then, $f(n)=\Omega(n^2)$ and $f(n)=O(n^2)$.

$f(n)=O(n^2)$ means that $\exists M>0, n_0 \geq 0$ such that $\forall n \geq n_0$:

$$f(n) \leq Mn^2 \Rightarrow n^2 \log_2{(\log_2 n)} \leq Mn^2 \Rightarrow \log_2{(\log_2 n)} \leq M, \text{ that is a contradiction.}$$

Suppose $n^2\log_2(\log_2 n) = O(n^c)$ with $c<2$.

Then that means that $\exists M >0, \exists n_0$ such that $\forall n \ge n_0$: $n^2\log_2(\log_2 n) < Mn^2$.
This implies $\forall n \ge n_0: M > \log_2(\log_2 n)$, which is a contradiction.

Therefore $n^2\log_2(\log_2 n) \ne O(n^c)$ with $c<2$. (Coffee)

Do we have this inequality: $n^2\log_2(\log_2 n) < Mn^2$, since from the definition, we have that $\exists M >0, \exists n_0$ such that $\forall n \ge n_0$: $n^2\log_2(\log_2 n) \leq M n^c$ and $c<2 \Rightarrow n^c<n^2$, so
$M n^c<M n^2$ ? (Thinking)

Also, is this: $\forall n \ge n_0: M > \log_2(\log_2 n)$ a contradiction, since we found a restriction for $n$, or am I wrong? (Worried)

Give it a try? (Thinking)

Could we do it like that? (Thinking)

Since $f(n)=\Theta(n^2 \log_2{(\log_2 n)})$, it follows that $f(n) \neq \Omega(n^c),c>2$.

Suppose $n^2 \log_2{(\log_2 n)}=\Omega(n^c), c>2$.

Then, that means that $\exists M>0, n_0 \geq 0$, such that $\forall n \geq n_0$:

$$n^2 \log_2{(\log_2 n)} > Mn^3 \Rightarrow \log_2{(\log_2 n)}>Mn$$

Is it right so far? How could we continue? (Thinking)

 

[I like Serena]

And could we prove it like that? (Thinking)

We suppose that $f(n)=\Theta(n^2)$.

Then, $f(n)=\Omega(n^2)$ and $f(n)=O(n^2)$.

$f(n)=O(n^2)$ means that $\exists M>0, n_0 \geq 0$ such that $\forall n \geq n_0$:

$$f(n) \leq Mn^2 \Rightarrow n^2 \log_2{(\log_2 n)} \leq Mn^2 \Rightarrow \log_2{(\log_2 n)} \leq M, \text{ that is a contradiction.}$$

Yep! (Nod)

Do we have this inequality: $n^2\log_2(\log_2 n) < Mn^2$, since from the definition, we have that $\exists M >0, \exists n_0$ such that $\forall n \ge n_0$: $n^2\log_2(\log_2 n) \leq M n^c$ and $c<2 \Rightarrow n^c<n^2$, so
$M n^c<M n^2$ ? (Thinking)

Also, is this: $\forall n \ge n_0: M > \log_2(\log_2 n)$ a contradiction, since we found a restriction for $n$, or am I wrong? (Worried)

Yes on both counts.
Sharp! (Speechless)

Could we do it like that? (Thinking)

Since $f(n)=\Theta(n^2 \log_2{(\log_2 n)})$, it follows that $f(n) \neq \Omega(n^c),c>2$.

Suppose $n^2 \log_2{(\log_2 n)}=\Omega(n^c), c>2$.

Then, that means that $\exists M>0, n_0 \geq 0$, such that $\forall n \geq n_0$:

$$n^2 \log_2{(\log_2 n)} > Mn^3 \Rightarrow \log_2{(\log_2 n)}>Mn$$

Is it right so far? How could we continue? (Thinking)

That is too strong.
We can't require a lower bound of $n^3$.
For instance $n^{2.5}$ might be a lower bound. (Worried)It should be:

Then, that means that $\exists M>0, n_0 \geq 0$, such that $\forall n \geq n_0$:
$$n^2 \log_2{(\log_2 n)} > Mn^c \Rightarrow \log_2{(\log_2 n)}>Mn^{c-2}$$To continue, what is:
$$\lim_{n\to \infty} \frac{n^2 \log_2{(\log_2 n)}}{n^{c-2}}$$
(Wondering)

 

[evinda]

That is too strong.
We can't require a lower bound of $n^3$.
For instance $n^{2.5}$ might be a lower bound. (Worried)It should be:

Then, that means that $\exists M>0, n_0 \geq 0$, such that $\forall n \geq n_0$:
$$n^2 \log_2{(\log_2 n)} > Mn^c \Rightarrow \log_2{(\log_2 n)}>Mn^{c-2}$$To continue, what is:
$$\lim_{n\to \infty} \frac{n^2 \log_2{(\log_2 n)}}{n^{c-2}}$$
(Wondering)

So, is it like that? (Thinking)

We suppose that $n^2 \log_2{(\log_2 n)}=\Omega(n^c), c>2$.
Then, that means that $\exists M>0, n_0 \geq 0$ such that $\forall n \geq n_0:$
$$n^2 \log_2{\log_2 n} \geq Mn^c \Rightarrow Mn^{c-2} \leq \log_2{\log_2 n}$$

$$\lim_{n \to +\infty} \frac{\log_2{\log_2 n}}{n^{c-2} } =\lim_{n \to +\infty} \frac{\frac{1}{n \cdot \log_2 n}}{(c-2) n^{c-3}}=\lim_{n \to +\infty} \frac{1}{(c-2)n^{c-2} \log_2{n} }=0$$

From this, we conclude that $\log_2{\log_2 n}=o(n^{c-2})$, so:

$$\forall N>0, \exists n_0 \text{ such that } \forall n \geq n_0: $$

$$\log_2{\log_2 n}<N n^{c-2}$$

Therefore, we cannot find a $M$, such that:

$$n^2 \log_2{\log_2 n} \geq Mn^c \Rightarrow Mn^{c-2} \leq \log_2{\log_2 n}$$

and, so we conclude that $f(n) \neq \Omega(n^c)$.Or have I done something wrong? (Thinking)

 

[I like Serena]

So, is it like that? (Thinking)

We suppose that $n^2 \log_2{(\log_2 n)}=\Omega(n^c), c>2$.
Then, that means that $\exists M>0, n_0 \geq 0$ such that $\forall n \geq n_0:$
$$n^2 \log_2{\log_2 n} \geq Mn^c \Rightarrow Mn^{c-2} \leq \log_2{\log_2 n}$$

$$\lim_{n \to +\infty} \frac{\log_2{\log_2 n}}{n^{c-2} } =\lim_{n \to +\infty} \frac{\frac{1}{n \cdot \log_2 n}}{(c-2) n^{c-3}}=\lim_{n \to +\infty} \frac{1}{(c-2)n^{c-2} \log_2{n} }=0$$

From this, we conclude that $\log_2{\log_2 n}=o(n^{c-2})$, so:

$$\forall N>0, \exists n_0 \text{ such that } \forall n \geq n_0: $$

$$\log_2{\log_2 n}<N n^{c-2}$$

Therefore, we cannot find a $M$, such that:

$$n^2 \log_2{\log_2 n} \geq Mn^c \Rightarrow Mn^{c-2} \leq \log_2{\log_2 n}$$

and, so we conclude that $f(n) \neq \Omega(n^c)$.Or have I done something wrong? (Thinking)

Looks good to me! (Nod)

 

[evinda]

Looks good to me! (Nod)

Great! Thank you mery much! (Party)