1 votes 1 votes The solution of the recurrence relation of $ T(n)=3T\left(floor \left(\frac{n}{4}\right)\right)+n$ is $O(n^{2})$ $O(n/g n)$ $O(n)$ $O(l g n)$ Algorithms ugcnetjune2014iii algorithms recurrence-relation + – makhdoom ghaya asked Jul 11, 2016 • recategorized Sep 30, 2018 by Pooja Khatri makhdoom ghaya 2.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes T(n) = 3T(floor (n/4))+ n ~ 3T(n/4)+n Apply Masters theorem n ^ (log 4 3) < n Hence T(n) = Θ(n) If T(n) = Θ(n) then T(n) = O(n) If T(n) = Θ(n) then T(n) = O(n 2 ) answer can be A and C Correct me if i am wrong sh!va answered Jul 11, 2016 sh!va comment Share Follow See all 2 Comments See all 2 2 Comments reply srestha commented Jul 11, 2016 reply Follow Share why O(n2) ? 0 votes 0 votes sh!va commented Jul 11, 2016 reply Follow Share f(n) = O(g(n)) means that if there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c g(n) for all n> n0. Simply speaking, for a value n, f(n) will be always less than or equal to g(n). In our case f(n) =n; then g(n) can be any thing that has value greater than equal to f(n) Example: n= O(n) n= O(n2) n/1000= O(n2) n= O(n 3) n2 = O(n2) n2+n = O(n2) 0 votes 0 votes Please log in or register to add a comment.