2 votes 2 votes 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. Algorithms recurrence-relation algorithms + – yuyutsu asked Jun 22, 2022 yuyutsu 603 views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments ankitgupta.1729 commented Jun 26, 2022 reply Follow Share @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 1 votes 1 votes yuyutsu commented Jun 27, 2022 reply Follow Share I appreciate your effort. Thank you. Great analysis. May I ask which book do you follow for studying recurrence or algo? Clrs? 0 votes 0 votes ankitgupta.1729 commented Jun 27, 2022 reply Follow Share Sorry, I don’t follow any book for studying algo now. I did it few years back. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes An easy approach to your recurrence relation …. akash_chauhan answered Jul 2, 2022 akash_chauhan comment Share Follow See all 0 reply Please log in or register to add a comment.