Fdtxjr

Deal with toxic manager when you can't quit

Why isn't the circumferential light around the M87 black hole's event horizon symmetric?

Match Roman Numerals

How to translate "being like"?

Can you cast a spell on someone in the Ethereal Plane, if you are on the Material Plane and have the True Seeing spell active?

What is the motivation for a law requiring 2 parties to consent for recording a conversation

What could be the right powersource for 15 seconds lifespan disposable giant chainsaw?

I am an eight letter word. What am I?

Dropping list elements from nested list after evaluation

How much of the clove should I use when using big garlic heads?

What does Linus Torvalds mean when he says that Git "never ever" tracks a file?

Can an undergraduate be advised by a professor who is very far away?

Why couldn't they take pictures of a closer black hole?

Accepted by European university, rejected by all American ones I applied to? Possible reasons?

A word that means fill it to the required quantity

How do you keep chess fun when your opponent constantly beats you?

How can I add encounters in the Lost Mine of Phandelver campaign without giving PCs too much XP?

Why don't hard Brexiteers insist on a hard border to prevent illegal immigration after Brexit?

Kerning for subscripts of sigma?

Loose spokes after only a few rides

Finding the area between two curves with Integrate

How do PCB vias affect signal quality?

Can there be female White Walkers?

Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?

Compute the worst case time complexity of the following algorithm, for i = 1 to n do for j = i to n^2 do print (i, j).

2

$begingroup$

for i = 1 to n do 

 for j = i to n^2 do 

 print (i, j).

So here is what I've got

$sum_i=1^n sum_j=i^n^2 $

$Csum_i=1^n sum_j=i^n^2 1 $

$Csum_i=1^n (n^2-i+1) $

$Csum_i=1^n n^2 - sum_i=1^n i + sum_i=1^n 1 $

Which becomes

$n^3 + dfracn(n+1)2 + n$

And since the term with the highest exponent dominates

$O( n^3)$

Now I'm a complete beginner, and I came up with this solution by going over my notes.

Was this the correct solution? If not how would I solve this problem?

discrete-mathematics computer-science computational-complexity

share|cite|improve this question

edited Mar 24 at 18:27

Max

1,0041319

asked Mar 24 at 6:06

BrownieBrownie

3327

$endgroup$

add a comment | 

2

$begingroup$

for i = 1 to n do 

 for j = i to n^2 do 

 print (i, j).

So here is what I've got

$sum_i=1^n sum_j=i^n^2 $

$Csum_i=1^n sum_j=i^n^2 1 $

$Csum_i=1^n (n^2-i+1) $

$Csum_i=1^n n^2 - sum_i=1^n i + sum_i=1^n 1 $

Which becomes

$n^3 + dfracn(n+1)2 + n$

And since the term with the highest exponent dominates

$O( n^3)$

Now I'm a complete beginner, and I came up with this solution by going over my notes.

Was this the correct solution? If not how would I solve this problem?

discrete-mathematics computer-science computational-complexity

share|cite|improve this question

edited Mar 24 at 18:27

Max

1,0041319

asked Mar 24 at 6:06

BrownieBrownie

3327

$endgroup$

add a comment | 

$begingroup$

for i = 1 to n do 

 for j = i to n^2 do 

 print (i, j).

So here is what I've got

$sum_i=1^n sum_j=i^n^2 $

$Csum_i=1^n sum_j=i^n^2 1 $

$Csum_i=1^n (n^2-i+1) $

$Csum_i=1^n n^2 - sum_i=1^n i + sum_i=1^n 1 $

Which becomes

$n^3 + dfracn(n+1)2 + n$

And since the term with the highest exponent dominates

$O( n^3)$

Now I'm a complete beginner, and I came up with this solution by going over my notes.

Was this the correct solution? If not how would I solve this problem?

discrete-mathematics computer-science computational-complexity

share|cite|improve this question

edited Mar 24 at 18:27

Max

1,0041319

asked Mar 24 at 6:06

BrownieBrownie

3327

$endgroup$

for i = 1 to n do 

 for j = i to n^2 do 

 print (i, j).

share|cite|improve this question

edited Mar 24 at 18:27

Max

1,0041319

asked Mar 24 at 6:06

BrownieBrownie

3327

share|cite|improve this question

edited Mar 24 at 18:27

Max

1,0041319

asked Mar 24 at 6:06

BrownieBrownie

3327

edited Mar 24 at 18:27

Max

1,0041319

edited Mar 24 at 18:27

Max

1,0041319

asked Mar 24 at 6:06

BrownieBrownie

3327

asked Mar 24 at 6:06

BrownieBrownie

3327

1 Answer
1

active

oldest

votes

2

$begingroup$

That's exactly how I would do it.

Looks fine to me.

share|cite|improve this answer

answered Mar 24 at 6:08

marty cohenmarty cohen

75.3k549130

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Alright what had me really psyched was $Csum_i=1^n (n^2-i+1)$ because I'm not really sure of the logic behind that step and kind of just adapted it from notes
  $endgroup$
  – Brownie
  Mar 24 at 6:09
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3160177%2fcompute-the-worst-case-time-complexity-of-the-following-algorithm-for-i-1-to%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

That's exactly how I would do it.

Looks fine to me.

share|cite|improve this answer

answered Mar 24 at 6:08

marty cohenmarty cohen

75.3k549130

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Alright what had me really psyched was $Csum_i=1^n (n^2-i+1)$ because I'm not really sure of the logic behind that step and kind of just adapted it from notes
  $endgroup$
  – Brownie
  Mar 24 at 6:09
  

  
  
  
  

add a comment | 

2

$begingroup$

That's exactly how I would do it.

Looks fine to me.

share|cite|improve this answer

answered Mar 24 at 6:08

marty cohenmarty cohen

75.3k549130

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Alright what had me really psyched was $Csum_i=1^n (n^2-i+1)$ because I'm not really sure of the logic behind that step and kind of just adapted it from notes
  $endgroup$
  – Brownie
  Mar 24 at 6:09
  

  
  
  
  

add a comment | 

$begingroup$

That's exactly how I would do it.

Looks fine to me.

share|cite|improve this answer

answered Mar 24 at 6:08

marty cohenmarty cohen

75.3k549130

$endgroup$

share|cite|improve this answer

answered Mar 24 at 6:08

marty cohenmarty cohen

75.3k549130

answered Mar 24 at 6:08

marty cohenmarty cohen

75.3k549130

answered Mar 24 at 6:08

marty cohenmarty cohen

75.3k549130