0 votes 0 votes While solving this recurrence T(n) = 2T(n/2 + 17) + n what is the need of 17 and how to go forward to solve this question using the method of master theorem ? Algorithms recurrence-relation master-theorem + – dragonball asked Jun 22, 2017 retagged Jun 25, 2022 by makhdoom ghaya dragonball 369 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 2 votes 2 votes I believe 17 is a constant which will not make a noticable difference when we compute Time complexity of this function. so we can ignore it. T(n)= 2T(n/2) + n now you can apply Master's theroem answer will be theeta(nlogn) Manu Thakur answered Jun 22, 2017 selected Jul 29, 2017 by Vijay Thakur Manu Thakur comment Share Follow See all 3 Comments See all 3 3 Comments reply dragonball commented Jun 22, 2017 reply Follow Share When n will be sufficiently large then we can ignore 17 however when n is small we should not ignore 17 . 0 votes 0 votes Manu Thakur commented Jun 22, 2017 reply Follow Share time complexity is never computed for the small values of n 0 votes 0 votes dragonball commented Jun 22, 2017 reply Follow Share Thanks :) 0 votes 0 votes Please log in or register to add a comment.