Big O Notation

Question

I'm trying to figure out big o notation. I have read several articles and YouTube videos and I'm guessing this is o(n^2).

# O(n^2)
def standard_deviation_1(numbers):
total = 0
count = 0
for number in numbers:
total += number
count += 1
avg = total / count
sum_squared_differences = 0
for number in numbers:
sum_squared_differences += (number - avg) ** 2
variance = sum_squared_differences / count
return variance ** 0.5

Answer 1

Lochard is correct, the second code is O(n^2) because you have two nested loops, so the iteration is executed n*n times (n is the size of the list)

Answer 2

You have two loops over the numbers, but they run sequentially after one another.
So this is O(2*n) time complexity.

For O(n^2) you would have two nested loops.

Answer 3

Chris If I am not confused, the second code repeats the process of finding the total and the count unnecessarily. Having the complexity increased from O(2n) to O(n²).

Answer 4

Tibor and Lochard,
Okay, thank you.
I was searching online for a good example of a nested for loop so that I could understand what you meant the first time.

Answer 5

Hi Tibor, in your honest opinion would you consider this code the same as the one above?

def standard_deviation_2(numbers):
sum_squared_differences = 0
count_numbers = 0
for number in numbers:
total = 0
count = 0
for value in numbers:
total += value
count += 1
avg = total / count
sum_squared_differences += (number - avg) ** 2
count_numbers += 1
variance = sum_squared_differences / count_numbers
return variance ** 0.5