1 1 vote .Let S1= ∑nr/2r (r=0 to logn-1) .S2= ∑r2r (r=0 to logn-1) what will be s1 and and s2 after expension Algorithms algorithms recurrence-relation descriptive + – eyeamgj 2.2k views answer comment Share Follow Print See all 2 Comments 2 2 Comments reply Shubhanshu commented Oct 4, 2017 reply Follow flag I thnk in S1 it should be 2^r rather than 2r. 0 0 replyShare eyeamgj commented Oct 13, 2017 reply Follow flag ya printing mistake.....it is 2^r. but solution? 0 0 replyShare Please log in or register to add a comment.
1 1 vote s1: part I s1:part II s2: Sorry for the horizontal image. I am not able to rotate it here!! Shuchi Sareen answered Jan 24, 2018 Shuchi Sareen comment Share Follow See 1 comment 1 1 comment reply abcgate2020 commented Nov 2, 2019 reply Follow flag no need to solve the recurrence relation just see the leading term in s1 and s2 . In s1 as the value of r is increased the terms keep on decreasing due to exponential function in denominator. So the term where r =1 I.e n/2 will be the leading and thus it will be the order of n. In S2 the last term where r=logn-1 is the leading term as exponential function is present in numerator so if you simplify it you would get Nolan. 1 1 replyShare Please log in or register to add a comment.
1 1 vote no need to solve it just see the leading term in s1 and s2 . In s1 as the value of r is increased the terms keep on decreasing due to exponential function in denominator. So the term where r =1 I.e n/2 will be the leading and thus it will be the order of n. In S2 the last term where r=logn-1 is the leading term as exponential function is present in numerator so if you simplify it you would get Nlogn. abcgate2020 answered Nov 2, 2019 abcgate2020 comment Share Follow 0 reply Please log in or register to add a comment.
