0

# Big O Notation

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

5 Answers

+ 3

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)

+ 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.

+ 2

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²).

+ 2

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.

0

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