-1

How does nested loop Big O is N^2 despite the below counter resulted in 30 steps ??

arr = [1,2,3,4,5]

counter = 0
for x in arr:
 counter += 1
 for y in arr:
    counter += 1

print(counter) # Equals 30
Eladtopaz
  • 1,036
  • 1
  • 6
  • 21
youhana
  • 318
  • 2
  • 16
  • 2
    Your counter is calculating N^2 + N. In big-O notation only the N^2 matters. – Samwise Aug 31 '21 at 14:36
  • @Samwise : Can you please share with me a document describing this bit of info? because N here isn't a constant .. therefore can't be ignored from my point of view, so If you have a document to be able to understand this, I would be thankful. – youhana Aug 31 '21 at 14:39
  • What do believe the relationship between `counter` and the big O should be? Big O is meant to give a broad idea of an algorithm's speed, but the `counter` variable can easily be tweaked in ways that don't effect the big O. – luther Aug 31 '21 at 14:42
  • 1
    In Big-O you take the dominating term which is N^2 here. – Frightera Aug 31 '21 at 14:43
  • 1
    https://en.wikipedia.org/wiki/Big_O_notation#Sum. The sum of two terms can be reduced to the maximum. max(N^2, N) = N^2. The reason you do this is that the point of big-O is to establish the upper bound. – Samwise Aug 31 '21 at 14:45
  • 1
    Another way to think about it is that what you're calculating is (N+1)*N. The 1 is a constant addend and so you can drop it, leaving N * N = N^2. – Samwise Aug 31 '21 at 14:48
  • @Samwise : Put it as an answer to upvote it. – youhana Aug 31 '21 at 14:49
  • 2
    Since it seems like the real question here is "how does Big O notation work?" I'm just going to mark this as a duplicate of a fairly canonical answer. In particular, read the **we only care about the most significant portion of complexity** section of that answer. – Samwise Aug 31 '21 at 14:50

2 Answers2

0

You should only count the counter in inner for loop. Because only in the inner loop, an instruction or an operation takes place. Hence, it will be 25.

mcgusty
  • 1,354
  • 15
  • 21
0

The thing that is confusing you likely is that you are incrementing the counter in the for loop with the X. Change you code to:

arr = [1,2,3,4,5]

counter = 0
for x in arr:
 # counter += 1    < --- omit this line
 for y in arr:
    counter += 1

print(counter) # Equals 30

You will see that the counter will now be 25. This better represents the question you are asking, which is why a nested for loop is O(N^2).

For this specific example, each element of the array is iterated through 5 times in the X for loop. If it were just this, this would be O(N). Due to the nested for loop, every time the for loop is iterated over, another for loop (y-loop) iterates over the entire list again, which is O(N) again.

Since both are O(N), you end up with a formula like so:

O(N * N) = O(N^2)

Here is a link to Big-O that I thought could be useful. It's in java, but the same concepts apply to python as well: https://developerinsider.co/big-o-notation-explained-with-examples/

Mitchnoff
  • 495
  • 2
  • 7