retagged by
1,675 views
1 votes
1 votes
.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
retagged by

2 Answers

1 votes
1 votes

s1: part I

s1:part II

s2:

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

1 votes
1 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.

Related questions

0 votes
0 votes
1 answer
1
Shreya2002 asked Oct 27, 2022
1,031 views
How to solve this recurrence relationT(n)= T(0.09n) + T(0.91n) + cnwhere c is constant and T(1)=1options are-
1 votes
1 votes
2 answers
2
srestha asked May 10, 2019
846 views
What is the solution of recurrence relation$T\left ( n \right )=T\left ( n-1 \right )+n$
2 votes
2 votes
2 answers
3
pradeepchaudhary asked Jul 14, 2018
9,136 views
Q.6 The time complexity of an algorithm T(n), where n is the input size, is given by— T(n)= T(n-1) + 1/n, if n>1 = 1, otherwise.The order of the algorithm is�...
0 votes
0 votes
2 answers
4
Devshree Dubey asked Apr 27, 2018
843 views
How to compute the nth term of fibonacci series 1,1,2,3,5........ ?