288 views
T(n) = 5T(n/3) + T(2n/3) + 1.

My answer is BigOmega(n) BigO(n). Am I right? This is a question I found on cs.stackexchange.

@yuyutsu

I told that so that we can get close to the solution.

Our recurrence is $u(k) = 5u(k-1) + u(k-1 + \log_3 2) + 1$

Suppose, $u(k) = 9^k,$ it means it should satisfy the given recurrence. So, if we put it in the right side of the recurrence then we get,

$5*9^{k-1} + 9^{k-1 + \log_3 2} + 1 = 5*9^{k-1} + 9^{k-1}*9^{\log_3 2} +1$

$= 5*9^{k-1} + 9^{k-1}*3^{\log_3 2^2} + 1 = 5*9^{k-1} + 4*9^{k-1} + 1 = 9*9^{k-1} + 1$

$=9^k + 1$

It means $u(k) = 9^k$ is not the absolutely correct solution. If $u(k) = 5u(k-1) + u(k-1 + \log_3 2)$ then it would be the correct solution.

But it is very close to the correct solution because $|u(k) – 9^k| = 1.$ Here you can say relative error is $1$ which is very less and constant. If you calculate $u(1),u(2),u(3),...$ then the difference between the actual value of $u(1),u(2),u(3),...$ and those values which solution $9^k$ provides, will be $1$ and that’s why we are saying $|u(k) – 9^k| = 1.$ and if $k$ is a very large value then also you will get difference as $1.$

So, you can say, $u(k) \approx 9^k$

Now, suppose, $u(k) = 8^k,$ if we put it in the right side of the recurrence, we get, $1.09*8^k + 1$

and now the relative error is $1.09*8^k + 1 – 8^k=0.09*8^k +1$ which is not a constant and gets bigger and bigger when $k$ is approaching to infinity.

Now, suppose, $u(k) = 7^k,$ if we put it in the right side of the recurrence, we get, $1.20*7^k + 1$

and now the relative error is $1.20*7^k + 1 – 7^k=0.20*7^k +1$ which is also not a constant and gets bigger and bigger when $k$ is approaching to infinity.

Now, suppose, $u(k) = 10^k,$ if we put it in the right side of the recurrence, we get, $0.92*10^k + 1$

and now the relative error is $|0.92*10^k + 1 – 10^k|=|-0.07*10^k +1|$ which is also not a constant and gets bigger and bigger when $k$ is approaching to infinity.

So, we get the less error in only $u(k) \approx 9^k$ and the less error we get, the more accurate we are :P

I appreciate your effort. Thank you. Great analysis. May I ask which book do you follow for studying recurrence or algo? Clrs?
Sorry, I don’t follow any book for studying algo now. I did it few years back.

1 vote
1
705 views
1 vote