1 votes 1 votes How n + n/2 + n/4 + .... 1 can approximate it as an infinite GP? Is it =1+2+4+8+..........n/4 + n/2 +n ? =O(2^n) ? related to an answer for: TIME COMPLEXITY Algorithms algorithms asymptotic-notation time-complexity + – Anu asked May 14, 2015 • retagged Jul 7, 2022 by Lakshman Bhaiya Anu 462 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 1 to n der are logn terms. apply GP sum formula = a(r^b-1)/(r-1) //b is no of terms in GP here a = 1, b = logn, r = 2 = 1*(2^(logn) -1)/(2-1) = n-1 // 2^logn = n = O(n) Digvijay Pandey answered May 14, 2015 Digvijay Pandey comment Share Follow See all 2 Comments See all 2 2 Comments reply Anu commented May 15, 2015 reply Follow Share Thank you :) Got it.but I think there are logn+1 terms.so sum=1*(2^l(ogn+1)-1)/(2-1) =2*2^logn -1 =2n-1 =O(n) got answer given by Palash Nandi 1 1 votes 1 votes Gate Mm commented Dec 17, 2015 reply Follow Share Howz 2 power logn =n? 0 votes 0 votes Please log in or register to add a comment.
