Bsrgvty

Why are the Democrats & Republicans so homogeneous in their opinions of impeaching Trump?

Why is there a preference to use the cumulative distribution function to characterise a random variable instead of the probability density function?

Solve unwanted white "waves" and "Pacman squares" in low-light picture - post using Google Photos

Is harmlessly appearing to be a school bus driver a crime?

Predicting y from log y as the dependent variable

An Ailing Assassin

What does "你舒服吗" mean in a relationship context?

At a conference, should I visit other people's posters during my poster session?

Sleep for 1000 years

What's the greatest number of hands I can have to annoy my mother-in-law with?

What is the density of supercooled LOX at −206 °C, as SpaceX uses it

Can we use a Cryptographic hash function to generate infinite random numbers?

System of equation

No transit zone at Linate airport. Couldn't get on connecting flight. Whose responsibility is it?

Elves, Hobbits and Dwarves

How did 達 (~tachi) come to mean `pluralize` something?

How do I force `sudo` to ask for a password each time when a specific command is used?

Is an Immune creature considered to have the condition without suffering its effects?

Is it safe to wear earplugs in flight?

Can you marry a girl in Stardew Valley if you are a girl?

How to calculate my anticipated peak amperage load?

Is it possible for nature to create bubble wrap?

Does the production of a Tesla battery produce as much CO2 as driving 200,000 km?

Is there an equivalent to the monkey grip feat in d&d 5e?

Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation

Solving $T(n)= 3T(fracn4) + ncdot lg(n)$ using the master theoremSolving recurrence relation with two recursive callsCases of Master TheoremSolving the recurrence T(n) = 4T(n/4) + n log n with the iterative methodSolving Recurrence Relation (quicksort )How to Solve the following Recurrence Equation?Approximating a series for asymptotic upper boundRecurrence Equation upper limit problemSolving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;

1

$begingroup$

I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same answer. My steps are below.

Given $T(1) = 1$, $T(2) = 1$ (Time taken is constant in these two cases)

I noticed that by unrolling a few times:
$$T(n) = 2left[2Tleft(fracn4right)+fracn2logfracn2right] + nlog n$$
$$T(n) = 2^2Tleft(fracn2^2right)+n logfracn2 + nlog n$$
$$T(n) = 2^2left[2T(fracn8)+fracn2logfracn4right]+n logfracn2 + nlog n$$
$$T(n) = 2^3Tleft(fracn8right)+2nlogfracn4+n logfracn2 + nlog n$$

This looks like it follows
$$T(n) = underbrace2^kTleft(fracn2^kright) + 2^knlogleft(fracn2^k+1right)_log_2n text times$$

I use the fact that $fracn2^k = 1$, so $k = log_2n$. Substituting this in: $2^kT(fracn2^k)$ = $2^log_2nT(1) = n$

Doing this summation as:
$$T(n)=n + nlog_2n+sum_k=0^log_2n-12^k n log_2left(frac n 2^k+1right)$$
$$T(n)=n + nlog_2n+nsum_k=0^log_2n-12^k log_2left(frac n 2^k+1right)$$
$$T(n)=n + nlog_2n+nsum_k=0^log_2n-12^k log_2(n-k+1)$$

This is where I get stuck, I have a feeling I messed something up somewhere and it is making this summation much harder to solve, but I am not sure where. Where did I go wrong?

recurrence-relation recursion big-o-notation

share|cite|improve this question

edited Sep 30 at 16:45

xskxzr

5,57533 gold badges1212 silver badges3838 bronze badges

asked Sep 30 at 14:21

CitutCitut

1333 bronze badges

$endgroup$

add a comment
 | 

1

$begingroup$

I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same answer. My steps are below.

Given $T(1) = 1$, $T(2) = 1$ (Time taken is constant in these two cases)

I noticed that by unrolling a few times:
$$T(n) = 2left[2Tleft(fracn4right)+fracn2logfracn2right] + nlog n$$
$$T(n) = 2^2Tleft(fracn2^2right)+n logfracn2 + nlog n$$
$$T(n) = 2^2left[2T(fracn8)+fracn2logfracn4right]+n logfracn2 + nlog n$$
$$T(n) = 2^3Tleft(fracn8right)+2nlogfracn4+n logfracn2 + nlog n$$

This looks like it follows
$$T(n) = underbrace2^kTleft(fracn2^kright) + 2^knlogleft(fracn2^k+1right)_log_2n text times$$

I use the fact that $fracn2^k = 1$, so $k = log_2n$. Substituting this in: $2^kT(fracn2^k)$ = $2^log_2nT(1) = n$

Doing this summation as:
$$T(n)=n + nlog_2n+sum_k=0^log_2n-12^k n log_2left(frac n 2^k+1right)$$
$$T(n)=n + nlog_2n+nsum_k=0^log_2n-12^k log_2left(frac n 2^k+1right)$$
$$T(n)=n + nlog_2n+nsum_k=0^log_2n-12^k log_2(n-k+1)$$

This is where I get stuck, I have a feeling I messed something up somewhere and it is making this summation much harder to solve, but I am not sure where. Where did I go wrong?

recurrence-relation recursion big-o-notation

share|cite|improve this question

edited Sep 30 at 16:45

xskxzr

5,57533 gold badges1212 silver badges3838 bronze badges

asked Sep 30 at 14:21

CitutCitut

1333 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same answer. My steps are below.

Given $T(1) = 1$, $T(2) = 1$ (Time taken is constant in these two cases)

I noticed that by unrolling a few times:
$$T(n) = 2left[2Tleft(fracn4right)+fracn2logfracn2right] + nlog n$$
$$T(n) = 2^2Tleft(fracn2^2right)+n logfracn2 + nlog n$$
$$T(n) = 2^2left[2T(fracn8)+fracn2logfracn4right]+n logfracn2 + nlog n$$
$$T(n) = 2^3Tleft(fracn8right)+2nlogfracn4+n logfracn2 + nlog n$$

This looks like it follows
$$T(n) = underbrace2^kTleft(fracn2^kright) + 2^knlogleft(fracn2^k+1right)_log_2n text times$$

I use the fact that $fracn2^k = 1$, so $k = log_2n$. Substituting this in: $2^kT(fracn2^k)$ = $2^log_2nT(1) = n$

Doing this summation as:
$$T(n)=n + nlog_2n+sum_k=0^log_2n-12^k n log_2left(frac n 2^k+1right)$$
$$T(n)=n + nlog_2n+nsum_k=0^log_2n-12^k log_2left(frac n 2^k+1right)$$
$$T(n)=n + nlog_2n+nsum_k=0^log_2n-12^k log_2(n-k+1)$$

This is where I get stuck, I have a feeling I messed something up somewhere and it is making this summation much harder to solve, but I am not sure where. Where did I go wrong?

recurrence-relation recursion big-o-notation

share|cite|improve this question

edited Sep 30 at 16:45

xskxzr

5,57533 gold badges1212 silver badges3838 bronze badges

asked Sep 30 at 14:21

CitutCitut

1333 bronze badges

$endgroup$

share|cite|improve this question

edited Sep 30 at 16:45

xskxzr

5,57533 gold badges1212 silver badges3838 bronze badges

asked Sep 30 at 14:21

CitutCitut

1333 bronze badges

share|cite|improve this question

edited Sep 30 at 16:45

xskxzr

5,57533 gold badges1212 silver badges3838 bronze badges

asked Sep 30 at 14:21

CitutCitut

1333 bronze badges

edited Sep 30 at 16:45

xskxzr

5,57533 gold badges1212 silver badges3838 bronze badges

edited Sep 30 at 16:45

xskxzr

5,57533 gold badges1212 silver badges3838 bronze badges

asked Sep 30 at 14:21

CitutCitut

1333 bronze badges

asked Sep 30 at 14:21

CitutCitut

1333 bronze badges

1 Answer
1

active

oldest

votes

2

$begingroup$

First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:

$$T(n) = 2T(fracn2) + nlog(n) = 2(2T(fracn2^2 + fracn2log(fracn2)) + nlog(n) = nlog(n) + nlog(fracn2) + 2^2T(fracn2^2) = nlog(n) + nlog(fracn2) + 2^2(2T(fracn2^3 + fracn2^2log(fracn2^2)) = nlog(n) + nlog(fracn2) + n log(fracn2^2) + 2^3T(fracn2^3)$$

Hence, we will have the following, if we suppose $T(1) = 0$, w.l.o.g:

$$T(n) = sum_i=0^log(n)nlog(fracn2^i) = n log(Pi_i=0^log(n)fracn2^i) = n log(fracn^logn2^fraclog(n) times (log(n) + 1)2) = n log(n) log(fracnsqrt2sqrtn) = n log(n)logfracsqrtnsqrt2 = Theta(n
log^2(n))$$

Be aware that, if we change the values of $T(1)$ and $T(2)$ to the given constant values, nothing changed in the asymptotic analysis.

share|cite|improve this answer

edited Sep 30 at 15:27

answered Sep 30 at 15:11

OmGOmG

2,66111 gold badge88 silver badges1717 bronze badges

$endgroup$

add a comment
 | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f115274%2fsolving-the-recurrence-relation-tn-2tn-2-nlog-n-via-summation%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:

$$T(n) = 2T(fracn2) + nlog(n) = 2(2T(fracn2^2 + fracn2log(fracn2)) + nlog(n) = nlog(n) + nlog(fracn2) + 2^2T(fracn2^2) = nlog(n) + nlog(fracn2) + 2^2(2T(fracn2^3 + fracn2^2log(fracn2^2)) = nlog(n) + nlog(fracn2) + n log(fracn2^2) + 2^3T(fracn2^3)$$

Hence, we will have the following, if we suppose $T(1) = 0$, w.l.o.g:

$$T(n) = sum_i=0^log(n)nlog(fracn2^i) = n log(Pi_i=0^log(n)fracn2^i) = n log(fracn^logn2^fraclog(n) times (log(n) + 1)2) = n log(n) log(fracnsqrt2sqrtn) = n log(n)logfracsqrtnsqrt2 = Theta(n
log^2(n))$$

Be aware that, if we change the values of $T(1)$ and $T(2)$ to the given constant values, nothing changed in the asymptotic analysis.

share|cite|improve this answer

edited Sep 30 at 15:27

answered Sep 30 at 15:11

OmGOmG

2,66111 gold badge88 silver badges1717 bronze badges

$endgroup$

add a comment
 | 

2

$begingroup$

First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:

$$T(n) = 2T(fracn2) + nlog(n) = 2(2T(fracn2^2 + fracn2log(fracn2)) + nlog(n) = nlog(n) + nlog(fracn2) + 2^2T(fracn2^2) = nlog(n) + nlog(fracn2) + 2^2(2T(fracn2^3 + fracn2^2log(fracn2^2)) = nlog(n) + nlog(fracn2) + n log(fracn2^2) + 2^3T(fracn2^3)$$

Hence, we will have the following, if we suppose $T(1) = 0$, w.l.o.g:

$$T(n) = sum_i=0^log(n)nlog(fracn2^i) = n log(Pi_i=0^log(n)fracn2^i) = n log(fracn^logn2^fraclog(n) times (log(n) + 1)2) = n log(n) log(fracnsqrt2sqrtn) = n log(n)logfracsqrtnsqrt2 = Theta(n
log^2(n))$$

Be aware that, if we change the values of $T(1)$ and $T(2)$ to the given constant values, nothing changed in the asymptotic analysis.

share|cite|improve this answer

edited Sep 30 at 15:27

answered Sep 30 at 15:11

OmGOmG

2,66111 gold badge88 silver badges1717 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:

$$T(n) = 2T(fracn2) + nlog(n) = 2(2T(fracn2^2 + fracn2log(fracn2)) + nlog(n) = nlog(n) + nlog(fracn2) + 2^2T(fracn2^2) = nlog(n) + nlog(fracn2) + 2^2(2T(fracn2^3 + fracn2^2log(fracn2^2)) = nlog(n) + nlog(fracn2) + n log(fracn2^2) + 2^3T(fracn2^3)$$

Hence, we will have the following, if we suppose $T(1) = 0$, w.l.o.g:

$$T(n) = sum_i=0^log(n)nlog(fracn2^i) = n log(Pi_i=0^log(n)fracn2^i) = n log(fracn^logn2^fraclog(n) times (log(n) + 1)2) = n log(n) log(fracnsqrt2sqrtn) = n log(n)logfracsqrtnsqrt2 = Theta(n
log^2(n))$$

Be aware that, if we change the values of $T(1)$ and $T(2)$ to the given constant values, nothing changed in the asymptotic analysis.

share|cite|improve this answer

edited Sep 30 at 15:27

answered Sep 30 at 15:11

OmGOmG

2,66111 gold badge88 silver badges1717 bronze badges

$endgroup$

share|cite|improve this answer

edited Sep 30 at 15:27

answered Sep 30 at 15:11

OmGOmG

2,66111 gold badge88 silver badges1717 bronze badges

answered Sep 30 at 15:11

OmGOmG

2,66111 gold badge88 silver badges1717 bronze badges

answered Sep 30 at 15:11

OmGOmG

2,66111 gold badge88 silver badges1717 bronze badges