1 votes 1 votes Let $T(n)$ be a function defined by $T(n) =1$ and $T(n)=2T (n/2) + \sqrt{n}$, which of the following is true? $T(n) = O(\sqrt{n})$ $T(n) = O(\log_2 n)$ $T(n) = O(n)$ $T(n) = O(n^2)$ Algorithms ugcnetcse-dec2012-paper3 algorithms recurrence-relation time-complexity + – go_editor asked Jul 12, 2016 • recategorized Oct 10, 2018 by Pooja Khatri go_editor 1.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 1 votes 1 votes Apply master theorem u get O(n) is answer. Prashant. answered Jul 12, 2016 • selected Sep 16, 2016 by Sankaranarayanan P.N Prashant. comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes According to Master's theorem T(n) =aT(n/b) + nc a=2, b=2 nc = √n => nc = n1/2 => c=1/2 1. if logba < c, T(n) = Θ(nc), 2. if logba = c, T(n) = Θ(nc log n), 3. if logba > c, T(n) = Θ(nlogba). Here logba > c, So T(n)= Θ(nlogba)= Θ(n1)= Θ(n) Roma_nagpal answered Jun 20, 2018 Roma_nagpal comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Explanation: n(logba) = n which is = n^(1-.5) = O(sqrt n) then by applying case 1 of master method we get T(n) = Θ(n) sivaranijalamanayani answered May 9, 2020 sivaranijalamanayani comment Share Follow See all 0 reply Please log in or register to add a comment.