Geek Answers Handbook

Solving a recursive relationship using the iteration method

Consider the following example:

T(n) = T(7n/8) + 2n

I assumed that T (1) = 0

and tried to solve it as follows

 T(n) = T(7n/8) + 2n = T(49n/64) + 2.(7n/8) + 2n = T(343n/512) + 2.(7n/8).(7n/8)+ 2.(7n/8) + 2n = T(1) + 2n ( (7n/8)^i + ..... + 1)

but I could not come to any conclusion about this. I am confused by what I have to do in the next step.

+4
source share
3 answers

Your approach sounds, but you will see what to do if you rewrite it a little differently:

 T(n) = T((7/8)^1 * n) + 2 * (7/8)^0 * n = T((7/8)^2 * n) + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n = T((7/8)^3 * n) + 2 * (7/8)^2 * n + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n . . . = T((7/8)^k * n) + 2 * n * sum j = 0 to k-1 (7/8)^j

Now let k tend to infinity and see what happens. This will help if you are familiar with geometric series .

+6
source

T (n) = T (7n / 8) + 2n = 2n * (1 + 7/8 + (7/8) ^ 2 + ... (7/8) ^ Z) + T (1) where Z = ?

The only trick is to find Z. I bet the magazine will help. Sorry, it's too late, and I do not think directly, but ... you do not need to add a few 2n.

Edit: Z - how many times do you need to multiply n by 7/8 until you get 1.

So n * 7 ^ Z / 8 ^ Z = 1

(7/8) ^ Z = 1 / n

(8/7) ^ Z = n

You want to solve for Z.

0
source

What you got on the last line is a geometric series , and there is a formula to simplify this amount.

0
source

More articles:


All Articles