2 votes 2 votes The solution of the reccurence relation $T(n) \leq \begin{cases} \theta(1) & \text{ if } n \leq 80 \\ T\bigg(\dfrac{n}{s} \bigg)+T \bigg(\dfrac{7n}{10}+6\bigg)+O(n) & \text{ if } n> 80 \end{cases}$ is $O(\lg n)$ $O(n)$ $O(n \lg n)$ None of the above Algorithms ugcnetcse-dec2015-paper3 algorithms recurrence-relation + – go_editor asked Aug 9, 2016 • edited Jun 4, 2020 by go_editor go_editor 1.9k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Sandeep Singh commented Dec 30, 2015 reply Follow Share what is recurrence relation here? 0 votes 0 votes Sanjay Sharma commented Jan 4, 2016 reply Follow Share T(n)<={ ⊖(1) if n<=80 T(n/s) +T(7n/10)+O(n) if n>80 0 votes 0 votes Hradesh patel commented Jun 4, 2020 reply Follow Share I think Question is incomplete 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Assuming that s is a constant or 5 is misprinted as s: Given question can be reduced as: T(n) = T([n/s] ) + T(7n/10 + 6) + O(n) ≤ c[n/s] + c(7n/10 + 6) + O(n) ≤ c((n/s) + 7cn/10 + 6c + O(n) ≤ cn We can say T(n T(n) =O(n) sh!va answered Aug 9, 2016 sh!va comment Share Follow See 1 comment See all 1 1 comment reply helloarw commented Jul 19, 2018 reply Follow Share bro ,how can i learn abt Recurrence relations,plz suggest sm books or online material -thanku 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Option 2 (Check out median of medians selection algorithm) Reference (Page 32) Chris Jason answered Sep 7, 2019 Chris Jason comment Share Follow See all 0 reply Please log in or register to add a comment.