How can I find the exact solution?

[evinda]

Hello! (Wave)

$$\text{ Find an asymptotic exact solution of the recurrence relation: } S(m)=S(m^{\frac{1}{r}})+1, m \geq 2, r>1,\text{ applying the master theorem.} \\ \text{ Then, find the exact solution of the recurrence relation, considering that } S(2)=0.$$

Applying the master theorem, I found that $S(m)=\Theta(\log_2{ \log_r m})$.
Am I right? (Thinking)

Then, I thought to find the exact solution, using the substitution method.
I found that $S(m)=S(m^{\frac{1}{r^k}})+k$.

The recursion ends, when $m^{\frac{1}{r^k}}=2 \Rightarrow k=\log_r{ \frac{1}{2}}$.

The $k$ I found is negative... but, it isn't possible that the level, at which the recursion ends is negative.. (Worried)

Have I done something wrong? (Thinking)

 

[I like Serena]

Hello! (Wave)

$$\text{ Find an asymptotic exact solution of the recurrence relation: } S(m)=S(m^{\frac{1}{r}})+1, m \geq 2, r>1,\text{ applying the master theorem.} \\ \text{ Then, find the exact solution of the recurrence relation, considering that } S(2)=0.$$

Applying the master theorem, I found that $S(m)=\Theta(\log_2{ \log_r m})$.
Am I right? (Thinking)

Hey! (Happy)

It looks about right.
But how did you apply the master theorem?
The recurrence relation is not of the form $T (n) = aT (n/b) + f(n)$ is it? (Wondering)

The recursion ends, when $m^{\frac{1}{r^k}}=2 \Rightarrow k=\log_r{ \frac{1}{2}}$.

The $k$ I found is negative... but, it isn't possible that the level, at which the recursion ends is negative.. (Worried)

Have I done something wrong? (Thinking)

I think you did not solve for $k$ properly. (Worried)

 

[evinda]

Hey! (Happy)

It looks about right.
But how did you apply the master theorem?
The recurrence relation is not of the form $T (n) = aT (n/b) + f(n)$ is it? (Wondering)

That's what I did:

We set $n=\log_r m \Rightarrow r^n=m \Rightarrow m^{\frac{1}{r}}=r^{\frac{n}{r}}$.

Then, we have $S(r^n)=S(r^{\frac{n}{r}})+1$ and we set $R(n)=S(r^n)$.

So:

$$R(n)=R \left ( \frac{n}{r}\right)+1$$

Now, applying the master theorem, we get that: $f(n)=1=\Theta(n^{\log_b a}) \Rightarrow R(n)=\Theta(n^{\log_b a} \log_2 n)=\Theta(\log_2 n) \Rightarrow S(m)=\Theta(\log_2{\log_r n})$

I think you did not solve for $k$ properly. (Worried)

I tried it again and I got: $k=\log_r{\log_2 n}$.. Is it right now? (Thinking)

 

[I like Serena]

That's what I did:

We set $n=\log_r m \Rightarrow r^n=m \Rightarrow m^{\frac{1}{r}}=r^{\frac{n}{r}}$.

Then, we have $S(r^n)=S(r^{\frac{n}{r}})+1$ and we set $R(n)=S(r^n)$.

So:

$$R(n)=R \left ( \frac{n}{r}\right)+1$$

Now, applying the master theorem, we get that: $f(n)=1=\Theta(n^{\log_b a}) \Rightarrow R(n)=\Theta(n^{\log_b a} \log_2 n)=\Theta(\log_2 n) \Rightarrow S(m)=\Theta(\log_2{\log_r n})$

Nice! (Clapping)

I tried it again and I got: $k=\log_r{\log_2 n}$.. Is it right now? (Thinking)

Yep! (Nod)

 

[evinda]

Nice! (Clapping)

Yep! (Nod)

So, is the exact solution of the recurrence relation equal to $\log_r{\log_2 m}$ ? (Thinking)

 

[I like Serena]

So, is the exact solution of the recurrence relation equal to $\log_r{\log_2 m}$ ? (Thinking)

What do you get if you substitute that in the recurrence relation? (Wondering)

 

[evinda]

What do you get if you substitute that in the recurrence relation? (Wondering)

We get $\log_r{\log_2 m}=\log_r{\log_2{m^{\frac{1}{r}}}}+1=\log_r \left ( \frac{1}{r} \cdot \log_2 m\right)+1=\log_r{\log_2 m}$

So, it is right, yes? (Smile)

 

[I like Serena]

We get $\log_r{\log_2 m}=\log_r{\log_2{m^{\frac{1}{r}}}}+1=\log_r \left ( \frac{1}{r} \cdot \log_2 m\right)+1=\log_r{\log_2 m}$

So, it is right, yes? (Smile)

Yes! (Party)

 

[evinda]

Yes! (Party)

Great! (Party) Thanks a lot! (Smile)

 

[evinda]

I think you did not solve for $k$ properly. (Worried)

Using the substitution method, do we find the exact solution and so we don't have to show that it is actually the solution, or do we just find a hypothesis of the solution? (Thinking)

 

[I like Serena]

Using the substitution method, do we find the exact solution and so we don't have to show that it is actually the solution, or do we just find a hypothesis of the solution? (Thinking)

Generally speaking, you don't find the exact solution but only a hypothesis.
I wouldn't treat this case any other way. (Nerd)That is because a derivation is usually of the form: $P \Rightarrow Q \Rightarrow R$.
This means that $P$ and $R$ are not necessarily equivalent.
So you have to verify if $R$ is really the solution by testing it against $P$.

For instance, if you have $m^{1/r} = 1$, you can raise both sides to the power $r$ and get: $m=1^r = 1$ which is true for any $r$.
However, the original equation requires that $r\ne 0$. (Worried)

 

[evinda]

Generally speaking, you don't find the exact solution but only a hypothesis.
I wouldn't treat this case any other way. (Nerd)That is because a derivation is usually of the form: $P \Rightarrow Q \Rightarrow R$.
This means that $P$ and $R$ are not necessarily equivalent.
So you have to verify if $R$ is really the solution by testing it against $P$.

For instance, if you have $m^{1/r} = 1$, you can raise both sides to the power $r$ and get: $m=1^r = 1$ which is true for any $r$.
However, the original equation requires that $r\ne 0$. (Worried)

So, you mean that we can use the substitution method, in order to find a hypothesis of the solution of the recurrence relation and then we have to verify it? If so, do we have to verify it, as we did in post #7 or do we have to do it in an other way? (Thinking)

 

[I like Serena]

So, you mean that we can use the substitution method, in order to find a hypothesis of the solution of the recurrence relation and then we have to verify it? If so, do we have to verify it, as we did in post #7 or do we have to do it in an other way? (Thinking)

Yes, the way you did it in post #7 is a proper verification. (Nod)
It validates that all the solutions that you found are actual solutions.

In effect you verified that: $P \Rightarrow Q \Rightarrow R \Rightarrow P$.
Since the circle has been completed, we can tell that $P \iff R$.

 

[evinda]

Yes, the way you did it in post #7 is a proper verification. (Nod)
It validates that all the solutions that you found are actual solutions.

In effect you verified that: $P \Rightarrow Q \Rightarrow R \Rightarrow P$.
Since the circle has been completed, we can tell that $P \iff R$.

A ok... (Nod)

In order to find the exact solution, we see that the recursion ends, when $m^{\frac{1}{r^k}}=2 \Rightarrow \lg{m^{\frac{1}{r^k}}}=1 \Rightarrow \frac{1}{r^k} \lg m=1 \Rightarrow r^k=\lg m \Rightarrow k=\log_r{\lg m}$

To get from the relation $r^k=\lg m$ to this one: $k=\log_r{\lg m}$, it must stand: $m \neq 1$. Do I have to write it? (Thinking)

 

[I like Serena]

A ok... (Nod)

In order to find the exact solution, we see that the recursion ends, when $m^{\frac{1}{r^k}}=2 \Rightarrow \lg{m^{\frac{1}{r^k}}}=1 \Rightarrow \frac{1}{r^k} \lg m=1 \Rightarrow r^k=\lg m \Rightarrow k=\log_r{\lg m}$

To get from the relation $r^k=\lg m$ to this one: $k=\log_r{\lg m}$, it must stand: $m \neq 1$. Do I have to write it? (Thinking)

This is not necessary, since it is given that $m \ge 2$. (Wasntme)

 

[evinda]

This is not necessary, since it is given that $m \ge 2$. (Wasntme)

Oh, yes... right! Thank you very much! (Smirk)