3 votes 3 votes n1/2+n1/2n1/4+n1/2n1/4n1/8+n1/2n1/4n1/8n1/16.....upto n terms reena_kandari asked Jul 15, 2017 reena_kandari 368 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply joshi_nitish commented Jul 15, 2017 reply Follow Share you want exact sum or some bound on this series ?? 0 votes 0 votes reena_kandari commented Jul 15, 2017 reply Follow Share I think upper boud in O(n)..but dont know how to solve this. 0 votes 0 votes joshi_nitish commented Jul 15, 2017 i edited by joshi_nitish Jul 15, 2017 reply Follow Share Tr(rth term)= n(1-1/2^r) sum(series) = ΣTr = Σn(1-1/2^r) (r varies from 1 to n) take n common from series,(as it is constant) sum(series)= nΣn-1/2^r......now series will look like sum(series)= n(1/n1/2 + 1/n1/4 + 1/n1/16.....), now consider the series inside bracket, even if i take each term as 1/n1/2^n (which will lead to maximum sum)....the series(inside bracket) will tend to n*(1/n1/2^n)= n(1-1/2^n) hence maximum sum(series)<= n*n(1-1/2^n) <= n(2-1/2^n) it is < O(n2) but i am not sure about O(n), therefore i will conclude it to O(n2), but i am not saying it cant be O(n), but i cant proove it... 1 votes 1 votes Akash Verma 1 commented Nov 12, 2017 reply Follow Share it seems too complex to solve. please someone explain it in brief? 0 votes 0 votes Please log in or register to add a comment.