Question

Big 0 question.

Why is the answer to this O(n^2),

If Mr. Fields lives to be N years old, and he drinks 1 ounce of brandy on his birthday, for every year he has been alive (30 oz on 30 birthday, 31 oz on his 31, how many ounces will he consume in his N years.

Answer 1

The answer on the key was o(n^2). The only reason I can rationalize would be that if we were to graph both functions as numbers, n would be too slow rising (AKA faster), where as n^2 would always be above (AKA slower algorithm). And I'm pretty sure thats the definition of Big 0, to have a function that models how the algorithm performs as N gets large. Do you think that reasoning is right? Or is there another logical way to think about it?

Answer 2

Yeah. Algorithm complexity.

Answer 3

the close formula to the sum

\[\sum_{i=1}^{n}i\]

its \[n(n+1)/2\]

thats \[n ^{2}/2 + n/2 \]

and thats \[O(n^{2})\]

Answer 4

Are you sure that's right though, I feel like that is just a formula. For example, if I have an array of size n, and I want to square all the elements, I could just do...

for(i=0;i<last;i++)
{
sum=(array[i])^2 + sum
}

The formula says there is a square in it, but I know this algorithm would be o(N)

Answer 5

because u are counting steps, and it would be O(N*cost of calculating square), but basic operations are normally ignored. Big O notation its just an upper bound of a function. In computer science its normally used to bound steps and that give an idea of the time of the algorithm.

Answer 6

Wait, after reading your reply fedep3, I realized I didn't fully understood the problem.

There is an old story about Gauss, who in elementary school found out about progressive arithmetic. So there is even a simplier answer.
n(n + 1)/2

Also, I am quite sure this is a O(1) solution because you can increase n by any size and would still take the same time.

An O(n) solution would be to sum everything in a loop, it would increase linearly with n.

Also, the computational complexity of finding the square of a number is of O(1), it is simply num * num. So finding a square is by no means exponential in complexity.

Hope it helps and clears some stuff about Big O.

Answer 7

I agree with you, fab, but here is the exact problem from the practice test. Do you think he possibly made an error on the answer sheet? Ps, I remember that gauss problem from like every math class I've ever taken! Gauss is the Bauss. aha

23. Sidney Fields is the great‐grand‐nephew of famed explorer and mountaineer, Sir Edmund Hilary. Mr. Fields recently told Margaret Kinsdale (a descendant of flag‐maker Betsy Ross) that on each of his birthdays he drinks a number of 1‐ounce shots of brandy equal to his age. Ms. Kinsdale expressed surprise at this because Mr. Fields is known to prefer drinking only pomegranate juice. Mr. Fields explained, however, that he made an exception on his birthday to commemorate his “Uncle Hilary”. If Mr. Fields lives to be N years old, how many ounces of brandy will he consume during his life?

(1) O(N) *(2) O(N^2 ) (3) O(2^N ) (4) O(N^1/k ) where k is the age at which he started the tradition (5) Betsy Ross could probably down a gallon of brandy before Sir Edmund could load his pipe

Answer 8

the answer its \[O(n^{2})\]

they arent asking how many steps, just the number of onces. U can get the anwers in O(1), but the answers (numbers of onces) its O(n^2).

Answer 9

How? Let's consider 3 years old( he is an alcoholic baby). With O(n^2), he should have consumed 9 (3^2) ounces, but he will have only consumed 6 (3+2+1)...

Answer 10

http://en.wikipedia.org/wiki/Big_O_notation

Read the definition. its an upper bound. The exact number its the close formula i gave before, but that number its O(n^2) and yea its different of n^2 as u could see. O(n^2) doesnt mean equals n^2. I recommend u to understand first the meaning of Big-O, u got the wrong idea of what it is.

Answer 11

fedep, the gauss progressive arithmetic thing is O(1), the normal loop and sum would be O(n), the only of the two I see there is O(n), I am inclined to point out that O refers to complexity, which can be found varying n size until you see how the curve or lack thereof forms.

Answer 12

Big-O DOESNT means complexity, have u read the wikipedia link i gave? its a mathematic tool/notation used to describe the complexity of a function, but it can be used in any other thing u want...

Definition:
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions

As u seem to dont understand ill make u a prove why the the gauss progressive arithmetic its O(n^2).

The formula its n(n+1)/2

The definition now ill show that n(n+1)/2 its O(n^2), i am NOT counting the number of steps.

Its easy to show that there exists an M where n(n+1)/2 <= M*n^2

with M = 1 u got that

And u can see that n(n+1)/2 ISNT O(1), u wont find a M...

i am refering to the number NOT the number of steps....

calculating n(n+1)/2, as its only 1 asigment with basic operations, so its O(1)

if u do the loop:

sum = 0;
for(int i = 0; i < n; i++)
sum *= i;

the number of steps its n basic operations and thats O(n)

In the problem, he isnt asking for complexity...., hes asking the number of onces, and that number its O(n^2)

hope this make clear my point

Answer 13

Big O() wouldn't be used like that. :/ Honestly you just repeated me.

Me:
"O refers to complexity"
You:
"its a mathematic tool/notation used to describe the complexity of a function"

Me:
" which can be found varying n size until you see how the curve or lack thereof forms."
You:
"the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions"

You:
"i am NOT counting the number of steps"
Neither I am, I am just saying that as n increases the complexity remains the same
O(1) in the case of the closed form \[n(n+1)/2\]
Or in the case of looping it increases linearly with n
O(n)

If in the problem he is asking for the number of ounces then the answer would be \[n(n + 1)/2\] or in your "notation"\[O((n^{2} + n)/2)\]

Answer 14

i wont debate, thats not the point here, still i think they are not so equal.

I saw this long ago in class, i did some excercise, i read the wikipedia definition and thats what i remembered. In the Cormen book from MIT u can get all the definitions Big-O isnt the only one. Am pretty sure that O(n^2) its the answer and my explanation its the reason.

Answer 15

I spoke with my professor. Here is the correct answer.

for (i=0;i<n;i++)
for (j=0; j<n;j++)
{
sum=sum +j;
}
drinks= drinks+sum;

Since it must do two loops, it would be O(n^2)

Thanks for all the help!!

Answer 16

I am actually disappointd at such an unoptimal solution, as I told you it depended on the implementation and the most appropriate answer wouldbe n(n + 1) / 2. Make the suggestion in class and see what happens.

Also, fedep3, O(n^2) was dependant on the implementation which as shown isn't reaally the best or the first that comes to mind.

Have a nice day you two.