Upper and Lower bound of the recursive relation

In summary, the conversation discusses the use of the master theorem in finding the asymptotic upper and lower bounds of a recursive relation. The participants consider the form of the relation and determine that the master theorem cannot be applied. They then suggest using substitution to solve the relation.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)

I have to define an asymptotic upper and lower bound of the recursive relation $T(n)=5 T(\frac{n}{5})+\frac{n}{ \lg n}$.

I thought that I could use the master theorem,since the recursive relation is of the form $T(n)=aT(\frac{n}{b})+f(n)$

$$a=5 \geq 1 , b=5>1 , f(n)=\frac{n}{ \lg n}$$

$$f'(n)=\frac{ \lg n-1}{ \lg^2 n}>0 \Rightarrow \lg n >1 \Rightarrow n>2$$

So, $f(n)$ is asymptotically positive and increasing $\forall n>2$.

$$n^{\log_b a}=n^{\log_5 5}=n$$

We see that $f(n) < n$

$$f(n)=O(n^{ \log_b a- \epsilon})=O(n^{1- \epsilon})$$

But how can we find the $\epsilon$ ? (Thinking) Or can't we apply in this case the master theorem? (Worried)
 
Physics news on Phys.org
  • #2
I think that the master theorem cannot be applied. (Shake)

But..we could do it with substitution,right? (Thinking)

We set $m= \log_5{n} \Rightarrow n=5^m$

Then,we have:

$$T(5^m)=5T(5^{m-1})+\frac{5^m}{m} \\ \Rightarrow \frac{T(5^m)}{5^m}=\frac{T(5^{m-1})}{5^{m-1}}+\frac{1}{m}$$

Let $S(m)=\frac{T(5^m)}{5^m}$

So:

$$S(m)=S(m-1)+\frac{1}{m} \\ S(m-1)=S(m-2)+\frac{1}{m-1} \\ \dots \\ \dots \\ S(2)=S(1)+\frac{1}{2} \\ + --------------- \\ \Rightarrow S(m)=S(1)+\left ( \frac{1}{2}+ \dots + \frac{1}{m}\right )$$

But,how could we continue? (Thinking)
 

Related to Upper and Lower bound of the recursive relation

What is an upper bound of a recursive relation?

An upper bound of a recursive relation is the largest possible value that the relation can take on. It serves as an upper limit for the values that the relation can generate.

What is a lower bound of a recursive relation?

A lower bound of a recursive relation is the smallest possible value that the relation can take on. It serves as a lower limit for the values that the relation can generate.

How are the upper and lower bounds of a recursive relation determined?

The upper and lower bounds of a recursive relation are typically determined by analyzing the recursive formula or algorithm that defines the relation. By looking at the pattern of values generated by the relation, the upper and lower bounds can be identified.

Why are upper and lower bounds important in recursive relations?

Upper and lower bounds are important in recursive relations because they provide valuable information about the behavior and properties of the relation. They can help determine the rate of growth or decay of the relation and can be useful in analyzing its overall behavior.

Can the upper and lower bounds of a recursive relation change?

Yes, the upper and lower bounds of a recursive relation can change depending on the initial conditions or parameters of the relation. They can also be affected by changes in the recursive formula or algorithm that defines the relation.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
861
  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
0
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
804
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Back
Top