The Gateway to Computer Science Excellence
+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
in Algorithms by Loyal (6.2k points) | 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)

No related questions found

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
198,558 comments
105,381 users