Computers and Technology, 03.02.2020 04:44 Brock2002

Give a big-o estimate for the number additions used in this segment of an algorithm.
t : = 0
for i : = 1 to n
for j : = 1 to n
t : = t + i + j
i understand the answer is o(n^2) but how?

Answers: 2

Show answers

Answers

Big-O notation is a way to describe a function that represents the n amount of times a program/function needs to be executed.

(I'm assuming that := is a typo and you mean just =, by the way)

In your case, you have two loops, nested within each other, and both loop to n (inclusive, meaning, that you loop for when i or j is equal to n), and both loops iterate by 1 each loop.

This means that both loops will therefore execute an n amount of times. Now, if the loops were NOT nested, our big-O would be O(2n), because 2 loops would run an n amount of times.

HOWEVER, since the j-loop is nested within i-loop, the j-loop executes every time the i-loop ITERATES.

As previously mentioned, for every i-loop, there would be an n amount of executions. So if the i-loop is called an n amount of times by the j loop (which executes n times), the big-O notation would be O(n*n), or O(n^2).

(tl;dr) In basic, it is O(n^2) because the loops are nested, meaning that the i-loop would be called n times, and for each iteration, it would call the j-loop n times, resulting in n*n runs.

A way to verify this is to write and test program the above. I sometimes find it easier to wrap my head around concepts after testing them myself.

Answer from: Quest

browsing like internet search? don't look at anything stupid. or set up restrictions on ur device's search engine. and if something suspicious comes up don't be dumb and click on it. i hope that's what ur question meant.

Answer from: Quest

we can all learn from our past mistakes because we all have different ways of learning different types of techniques. my way may or may not another classmate remember and have the repetition to acknowledge such standard. such as remembering acronyms. using abbreviations to us remember keep things in order in our memory. this us figure out what comes next in the sequence. if so, what we have is a sentence of just letters all in caps. we either know the meaning or have no idea what it stands for. most of the time we know the meaning and context. but most of us who don't know, should learn by having a quick glance at what needs to be remembered. such as repetition in the memory for acronyms. one way that me, is the fact that i'm always doing math and english assignments. so we have to remember specific meanings such as soapstone for documents, such as citing correctly. or pemdas for doing the equations correctly, even if it's the super long way. this works for everyone. you just have to find what works for you by practicing and repetition daily.

Other questions on the subject: Computers and Technology

Computers and Technology, 22.06.2019 02:00, alexabessin

Aisha has finished working on a word processing document that contains 15 pages. she has added some special elements in the first three pages, page 9 and 10, and page 15 from the document. she wants to print only these pages to see how they look. which option is the correct way to represent (in the print dialog box) the pages that aisha wants to print?

Answers: 3

continue

Computers and Technology, 22.06.2019 11:00, yentel110306

When building customer relationships through email what should you not do? question 2 options: utilize proper grammar, spelling, and punctuation type in all capital letters use hyperlinks rather than attachments respond to all emails within 24 hours

Answers: 1

continue

Computers and Technology, 23.06.2019 06:00, ashleyd198308

Respond to the following in three to five sentences. select the workplace skill, habit, or attitude described in this chapter that you believe is most important for being a successful employee.

Answers: 1

continue

Computers and Technology, 23.06.2019 21:00, shawnnoteman1234

Which task uses a simple parameter?

Answers: 1

continue

You know the right answer?

Give a big-o estimate for the number additions used in this segment of an algorithm.
t : = 0