CODEWITHSUNDEEP
algorithmtimetime-complexity
Shubham Ugare
Shubham Ugare

Reputation: 103

A recurrence relation

I generally solve recurrence relations using master method.If it doesn't work then I try substitution method or recurrence tree method.The latter approaches take more time.Recently I came across some recursive relation which I cannot solve using normal method.I don't want rigorous answer(If possible then it's even better). I just want to know if there is any method which will get bounds for this recursive equations.

1) T(n)=T(n/10)+T(9*n/10)+1

2) T(n)=T(n^1/2)+T(n-n^1/2)+c*n

Upvotes: 0

Views: 214

Answers (1)

user1196549
user1196549

Reputation:

For 1), the Master Theorem has a generalization for a sum of T(α.n) in the right-hand side. See https://fr.wikipedia.org/wiki/Master_theorem#Extension (in French).

As the non-homogeneous term is 1, you can try a linear solution, a.n + b. Then,

a.n + b = a.n/10 + b + a.9n/10 + b + 1

which works for any a, and b=-1.

For 2), I have no clue, the argument n - √n makes it pretty hard. A linear form doesn't work.

Upvotes: 1

Related Questions