1 votes 1 votes The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $ = p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$ Algorithms nielit2017oct-assistanta-cs algorithms recurrence-relation time-complexity master-theorem + – admin asked Apr 1, 2020 • edited Aug 29, 2020 by soujanyareddy13 admin 1.3k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments raja11sep commented Dec 21, 2021 reply Follow Share Use back substitution. 0 votes 0 votes DAWID15 commented Dec 21, 2021 reply Follow Share Manually means by using the tree approach. Just as we do forr merge sort. 0 votes 0 votes akash_chauhan commented Jul 3, 2022 reply Follow Share bro, actually we are not dividing the input size of n into 8 parts. here , a function takes an input of size of n , and by definition of the the above recur. relation it calls 8 function of its type but here with size = n/2. and, subsequently each of these call 8 funtion of size= n/4. and for every level calling cost = (n). hope yu understand. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes We can directly apply master’s theorem on this to get T(n). T(n) = aT(n/b)+ f(n) a>=1, b>1 and If f(n) is Ɵ(n^d) d>=0 then, if a<b^d then T(n) = Ɵ(n^d) elif a==b^d then T(n) = Ɵ(n^d logn) elif a>b^d then T(n) = Ɵ(n^(logab) Here, a = 8; b = 2; d = 1 and, a>$b^{d}$ Therefore, T(n) = Ɵ(n$\log_{a} b$) = Ɵ(n$\log_{2} 8$) = Ɵ($n^{3}$) meakshaymishra answered May 17, 2021 meakshaymishra comment Share Follow See all 0 reply Please log in or register to add a comment.