+1 vote
481 views
.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
| 481 views
0
I thnk in S1 it should be 2^r rather than 2r.
0
ya printing mistake.....it is 2^r.   but solution?

## 2 Answers

+1 vote

s1: part I

s1:part II

s2:

Sorry for the horizontal image. I am not able to rotate it here!!

by (37 points)
0

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.

0 votes

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.

by (19 points)