Question

Struggling with Big O Notation...

I'm trying to figure out a few things with Big O. The first is I don't know when I need to multiply or add when trying to find the Big O value.

For example, refer to the below psuedocode:

function sum(list):
sum = 0;
foreach element in list:
current = element
add current to sum
sum = sum * 1
return sum
endfunction

So two questions:
sum = sum * 1... Is this counted as 1 operation, or as two (assignment, and multiplication)?

Apparently it's 1 + n * 2 + 2 = 2n + 3, ignoring coefficients, it is O(n). But...

So, is the sum = sum * 1 counted as 1 or 2 operations? It looks like in the above its counted as 1? Why? This is from: http://i.imgur.com/u0dUTlK.png

Also, I'm not sure when I should multiply or add to the formula, i.e. why is it 1 + n, and n * 2? The only reasoning I can see for it is that since it's a loop, it considers the TOTAL operations that are being made, i.e. if the length of the list was 50 elements, it would be 50 * 2 = 100 operations in total, thus 2n (and if there were 4 operations in each iteration it would be 4n)... Is that right? Thanks.

Answer 1

the reason that
```
sum = sum * 1
```
is two operations is exactly what you said: it is an assignment and a multiplication. It could also be written
```
sum * 1
sum = sum
```
it may be more clear with the += notation, in that
```
sum += 1
```
is the same as
```
sum = sum + 1
```
the compiler or interpreter works from right to left on each line with assignments, so first the operating system adds 1 to contents of the variable
```
sum
```
then stores the result in that variable with an assignment. (this would be even more apparent if you looked at the assembly language code)

As far as your explanation of why it's n*2 operations when we iterate over that loop, your explanation is correct.

Answer 2

Okay thanks! So when it comes to the equation: 1 + n * 2 + 2 = 2n + 3
Is this actually wrong?

Instead, would it be:

function sum(list):
sum = 0; //Assignent, 1 operation O(1)
foreach element in list: //Loop N operation O(N)
current = element //Assignment, 1 operation O(1)
add current to sum // Assignment and Addition, 2 Operations 0(1) + O(1)
//End of loop
sum = sum * 1 //Assignment and Multiplication, 2 Operations O(1) + O(1)
return sum //Return, 1 Operation O(1)
endfunction

Thus, 1 + N * 3 + 3
= 3N + 4

Removing Coefficients and the "+4": Answer is O(N)


(Note that in the example the author said it was (1 + n * 2 + 2)
However I think it's (1 + N * 3 + 3)

So am I correct or missing something fundemetal? Thanks.

Answer 3

Your idea seems mostly correct, though there is one subtlety you overlooked, and your notation is incorrect. using big-O notation, O(1)=O(2), sometimes written 0(c) where c represents some unspecified constant. this notation only concerns itself with the upper bound running time of the algorithm as a whole; it has nothing to do with the actual number of steps. For instance, I could write a program with 10^10 hard-coded print statements. It may take 10^10 steps to run, but in big-O notation it is still O(1) or O(c), however you prefer to write it.

Answer 4

to write code on here, btw, write tho code as follows
(```)
some code
(```)
(remove parentheses)
```
some code
```

Answer 5

anyway, one subtlety is that each iteration trough the loop
```
foreach element in list:
```
actually involves an assignment for the temporary variable "element" at the beginning each time. Hence there are actually 3 operations in each iteration being performed in the code
```
function sum(list):
sum = 0; //Assignent, 1 operation
foreach element in list: //Loop N operations, 1 assignment each time
current = element //Assignment, 1 operation
add current to sum // Assignment and Addition, 2 Operations
```