Why can we not apply the theorem?

In summary: 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)Yes, exactly. We can use the fact that $c<2$ to make the inequality strict. (Coffee)Also, is this: $\forall n \ge n_0: M > \
  • #1
evinda
Gold Member
MHB
3,836
0
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)
 
Physics news on Phys.org
  • #2
evinda said:
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)
 
  • #3
I like Serena said:
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)$
 
Last edited:
  • #4
If so, how could I do this? (Thinking)
 
  • #5
evinda said:
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$$

evinda said:
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$.
 
  • #6
I like Serena said:
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)

I like Serena said:
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)
 
  • #7
evinda said:
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. :confused:
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)
 
  • #8
I like Serena said:
For what it is worth, wikipedia gives a more general second case. :confused:

In my notes, at the the second case, it is $f(n)=\Theta(n^{\log_b a})$.. (Wasntme)
I like Serena said:
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? :confused:

How could we prove it explicitly? (Thinking)
 
  • #9
evinda said:
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? :confused:

Give it a try? (Thinking)
 
  • #10
I like Serena said:
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.}$$
I like Serena said:
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)

I like Serena said:
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)
 
  • #11
evinda said:
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)
 
  • #12
I like Serena said:
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)
 
  • #13
evinda said:
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)
 
  • #14
I like Serena said:
Looks good to me! (Nod)

Great! Thank you mery much! (Party)
 

Related to Why can we not apply the theorem?

1. Why is the theorem not applicable in all situations?

The theorem is a mathematical concept that is based on certain assumptions and conditions. It may not be applicable in all situations because these assumptions and conditions may not be met. Additionally, the theorem may only be applicable to a specific type of problem or data set.

2. What are the limitations of the theorem?

The limitations of the theorem can vary depending on the specific theorem in question. However, some common limitations may include assumptions about the data being normally distributed, the presence of outliers, or the linearity of the relationship between variables. It is important to carefully consider these limitations before applying a theorem in a particular situation.

3. Can the theorem be modified or adjusted for different scenarios?

In some cases, the theorem may be modified or extended to apply to different scenarios. However, this requires a thorough understanding of the underlying principles and assumptions of the theorem, and may not always be possible. It is best to consult with an expert or conduct further research before attempting to modify a theorem.

4. Are there alternatives to using the theorem?

Yes, there are often alternative methods or approaches that can be used in place of a theorem. These may include different statistical tests, models, or algorithms. It is important to carefully consider the goals and limitations of the analysis before deciding on the most appropriate method to use.

5. How can we determine when the theorem is applicable?

Determining when the theorem is applicable requires a thorough understanding of the assumptions and conditions of the theorem, as well as the data and problem at hand. It is important to carefully evaluate these factors and consider whether they are met before applying the theorem. Consulting with experts or conducting further research can also help in determining the applicability of a theorem.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
857
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
491
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
759
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Back
Top