I am currently studying Divide and conquer. I have been reading algorithm design by Jon Kleinberg along with the lecture slides from our lecturer. I am stuck with the part where they teach us about the solution of divide and conquer recurrences. I could not understand how they got the answer. It goes like this. Fix a>0, b>1 and consider T(n)=aT(n/b)+f(n) (when n>n_0), n_0=c. First solve this when nn0 is a power of b: put U(i)=T(n_0b^i) and g(i)=f(n_0b^i) Get U(i)=aU(i−1)+g(i) (when i>0), U(0)=c) iterate to obtain enter image description here Important special case: f(n)=n^p for some fixed p. Write B=b^p. What I do not understand is that when they said "when nn0 is a power of b:", n should be something like n=n0bi. After that when we substitute T(n) with the n=n_0b^i, it should be somethin

Gauge Odom

Gauge Odom

Answered question

2022-09-04

I am currently studying Divide and conquer.
I have been reading algorithm design by Jon Kleinberg along with the lecture slides from our lecturer.
I am stuck with the part where they teach us about the solution of divide and conquer recurrences.
I could not understand how they got the answer.
It goes like this.
Fix a>0, b>1 and consider
T(n)=aT(nb)+f(n) (when n>n0), n0=c.
First solve this when nn0 is a power of b:
put U(i)=T(n0bi) and g(i)=f(n0bi).
Get
U(i)=aU(i−1)+g(i) (when i>0), U(0)=c)
iterate to obtain
enter image description here
Important special case: f(n)=np for some fixed p.
Write B=bp.
What I do not understand is that when they said "when nn0 is a power of b:", n should be something like n=n0bi. After that when we substitute T(n) with the n=n0bi, it should be something like
T(n0bib)
How did they end up with T(n0bi)?
Also they said iterate to obtain
enter image description here
How did they obtain that? They did not provide any walk through that I could follow on how to get that..

Answer & Explanation

Azul Lang

Azul Lang

Beginner2022-09-05Added 20 answers

If f(n) is monotone increasing (normally a given in divide-and-conquer cases), it is clear that T(n) is also monotone increasing. If we just consider n=n0bk, the values will interpolate and for asymptotic behaviour we are clear. Define tk=T(n0bk), so that k=logbn, and you can write the recurrence as:
tk=atk−1+f(n0bk)
To solve this, divide by ak to get:
tkak−tk−1ak−1tkak−t1tkT(n)=f(n0bk)ak=∑2≤j≤kf(n0bj)aj=akt1+ak∑2≤j≤kf(n0bj)aj=alogbnT(n0b)+alogbn∑2≤j≤logbnf(n0bj)aj=nlogbaT(n0b)+nlogba∑2≤j≤logbnf(n0bj)aj
Here we used:
alogbn=blogba⋅logbn=(blogbn)logba=nlogba
How this behaves as n→∞ now depends on the two terms on the right.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in High school statistics

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?