Mixing
![Plotting the sum of prime factors of integers with rational exponents [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Solving a summation of an average case analysis
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I was going over some review material for my Algorithms class that I would eventually take during spring semester and came upon this summation equation. Its an average case analysis of an algorithm that finds Max and Min of an array. What I can't figure out is how the summation goes from the top to the harmonic series. It later uses the series to justify the $theta$ ln n
$sum_i=2^n ((1over i) times 1 + (i-1)over i times 2)$
= $sum_i=2^n (2-1over i)$
= $2(n-1) - sum_i=2^n 1over i$
= $2n - 1 - sum_i=1^n 1over i$
discrete-mathematics computer-science
edited Jul 19 at 9:53
BDN
573417
asked Jul 19 at 0:51
Kamran Raza
31
add a comment |Â
up vote
0
down vote
favorite
I was going over some review material for my Algorithms class that I would eventually take during spring semester and came upon this summation equation. Its an average case analysis of an algorithm that finds Max and Min of an array. What I can't figure out is how the summation goes from the top to the harmonic series. It later uses the series to justify the $theta$ ln n
$sum_i=2^n ((1over i) times 1 + (i-1)over i times 2)$
= $sum_i=2^n (2-1over i)$
= $2(n-1) - sum_i=2^n 1over i$
= $2n - 1 - sum_i=1^n 1over i$
discrete-mathematics computer-science
edited Jul 19 at 9:53
BDN
573417
asked Jul 19 at 0:51
Kamran Raza
31
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I was going over some review material for my Algorithms class that I would eventually take during spring semester and came upon this summation equation. Its an average case analysis of an algorithm that finds Max and Min of an array. What I can't figure out is how the summation goes from the top to the harmonic series. It later uses the series to justify the $theta$ ln n
$sum_i=2^n ((1over i) times 1 + (i-1)over i times 2)$
= $sum_i=2^n (2-1over i)$
= $2(n-1) - sum_i=2^n 1over i$
= $2n - 1 - sum_i=1^n 1over i$
discrete-mathematics computer-science
edited Jul 19 at 9:53
BDN
573417
asked Jul 19 at 0:51
Kamran Raza
31
I was going over some review material for my Algorithms class that I would eventually take during spring semester and came upon this summation equation. Its an average case analysis of an algorithm that finds Max and Min of an array. What I can't figure out is how the summation goes from the top to the harmonic series. It later uses the series to justify the $theta$ ln n
$sum_i=2^n ((1over i) times 1 + (i-1)over i times 2)$
= $sum_i=2^n (2-1over i)$
= $2(n-1) - sum_i=2^n 1over i$
= $2n - 1 - sum_i=1^n 1over i$
discrete-mathematics computer-science
edited Jul 19 at 9:53
BDN
573417
asked Jul 19 at 0:51
Kamran Raza
31
edited Jul 19 at 9:53
BDN
573417
edited Jul 19 at 9:53
BDN
573417
edited Jul 19 at 9:53
BDN
573417
573417
asked Jul 19 at 0:51
Kamran Raza
31
asked Jul 19 at 0:51
Kamran Raza
31
asked Jul 19 at 0:51
Kamran Raza
31
31
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
Because
$fraci-1icdot 2
=(1-frac1i)cdot 2
=2-frac2i
$.
answered Jul 19 at 1:53
marty cohen
69.2k446122
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
Because
$fraci-1icdot 2
=(1-frac1i)cdot 2
=2-frac2i
$.
answered Jul 19 at 1:53
marty cohen
69.2k446122
add a comment |Â
up vote
0
down vote
accepted
Because
$fraci-1icdot 2
=(1-frac1i)cdot 2
=2-frac2i
$.
answered Jul 19 at 1:53
marty cohen
69.2k446122
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
Because
$fraci-1icdot 2
=(1-frac1i)cdot 2
=2-frac2i
$.
answered Jul 19 at 1:53
marty cohen
69.2k446122
Because
$fraci-1icdot 2
=(1-frac1i)cdot 2
=2-frac2i
$.
answered Jul 19 at 1:53
marty cohen
69.2k446122
answered Jul 19 at 1:53
marty cohen
69.2k446122
answered Jul 19 at 1:53
marty cohen
69.2k446122
answered Jul 19 at 1:53
marty cohen
69.2k446122
69.2k446122
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856153%2fsolving-a-summation-of-an-average-case-analysis%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password