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

14th Jan 2023, 4:38 PM
Chris
Chris - avatar
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)
14th Jan 2023, 6:25 PM
Tibor Santa
Tibor Santa - avatar
+ 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.
14th Jan 2023, 5:05 PM
Tibor Santa
Tibor Santa - avatar
+ 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ÂČ).
14th Jan 2023, 6:20 PM
Lochard
Lochard - avatar
+ 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.
14th Jan 2023, 6:53 PM
Chris
Chris - avatar
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
14th Jan 2023, 5:57 PM
Chris
Chris - avatar