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 602 views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply yuyutsu commented Jun 23, 2022 reply Follow Share @GO Classes 0 votes 0 votes Sachin Mittal 1 commented Jun 23, 2022 reply Follow Share You can show solution 0 votes 0 votes DEBANJAN DAS2k commented Jun 25, 2022 reply Follow Share Is my answer correct? @Sachin Mittal 1 0 votes 0 votes ankitgupta.1729 commented Jun 26, 2022 i edited by ankitgupta.1729 Jun 26, 2022 reply Follow Share $T(n) \in \Omega(n)$ and $ T(n) \in O(n)$ means $T(n) \in \Theta(n)$ which is not possible and it can be proved very easily. It is easy to prove that $T(n) \in \Theta(n^{>1.6})$ and there might be some difficulty to show $T(n) \in \Theta(n^2)$ by methods such as back-substitution, recurrence tree method unless you guess correctly and then prove it or you know the Akra-Bazzi method. Here, $T(n) = 5T(\frac{n}{3}) + T(\frac{2n}{3}) + 1$ Let, $n= 3^k \implies k = \log_3 n$, So, $T(3^k) = 5T(3^{k-1}) + T(2*3^{k-1}) + 1$ Let, $T(3^k) = u(k)$ Hence, $$u(k) = 5u(k-1) + u(k-1 + \log_3 2) + 1$$ Now, if we do some approximation and try to get the correct answer. If we remove/ignore the term $\log_3 2 \approx 0.631 $ in $u(k-1 + \log_3 2), $ we get, $u(k) = 6u(k-1) + 1,$ $u(k)= \Theta(6^k)$ which means $T(n) = T(3^k) = u(k) = \Theta(6^k)= \Theta(6^{\log_3 n}) = \Theta(n^{\log_3 6}) = \Theta(n^{1.631})$ Since, we removed/ignored the term $\log_3 2 \approx 0.631 $ in $u(k-1 + \log_3 2),$ it means actually $T(n) \in \Theta(n^{>1.631})$ So, your claim $T(n) \in \Theta(n)$ is actually incorrect. Now, to get the correct answer, instead of $6^k,$ we can check $7^k, 8^k, 9^k,10^k..$ Here, we need not have to check many values because we are near to our correct answer. Because if we take $u(k) \approx 6^k$ then $|6^k – u(k)|$ is more as compared to $|9^k-u(k)|$ for $k=1,2,3,..$, assuming $u(0)=1$ and when we go towards $9^k$ then difference between $9^k$ and $u(k)$ getting towards one for sufficiently large $k.$ and so, $u(k) \in \Theta(9^k) = \Theta(3^{2k}) $ And so, $u(k) = T(3^k) = T(n) \in \Theta(3^{2\log_3 n}) = \Theta(3^{\log_3 n^2}) $ So, $T(n) \in \Theta (n^2)$ [It might be difficult to solve $u(k) = 5u(k-1) + u(k-1 + \log_3 2) + 1$ by back-substitution/recurrence tree method but if we do some approximation then we will tend to find the correct answer. For example, we can approximate $\log_3 2$ by $0.6$ instead of $0.631…$ and so we get, $u(k) = 5u(k-1) + u(k-\frac{2}{5}) + 1 \implies u(k) \approx 8.66^k$ which is close to $9^k.$ ] 1 votes 1 votes yuyutsu commented Jun 26, 2022 reply Follow Share Thankyou for your answer. as far as I can remember even the answer on the site where I came across this question was also n^2. This is fantastic. Thankyou. Very nice explained. Could you please elaborate on why you suggest to try with 7^k or 9^k? 0 votes 0 votes yuyutsu commented Jun 26, 2022 reply Follow Share Thankyou Debanjan. 0 votes 0 votes 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.