CODEWITHSUNDEEP
pythonalgorithmbig-o
DougM
DougM

Reputation: 930

What is the worst-case big-O time complexity for this code?

I had a quiz in my class and didn't do so well on it. I'm looking to find out if someone can explain to me what I did wrong here - our professor is overwhelmed with office hours as we moved online so I thought I'd post here.

def functionB(n):
  for i in range(1,6):
    for j in range(i,6):
      n = n // 2
  return n

I gave the following answer:

The above function is O(n^2) because of the nested for-loops. Although the value of n is being cut in half upon each iteration, it does not have an impact on the actual run time of the code.

I was given 3/10 for it but unfortunately there is no explanation so I'm unsure of what I got wrong and why. Is there anyone here who can explain the correct answer to me?

Upvotes: 1

Views: 425

Answers (2)

VIKRAM SINGH CHOUHAN
VIKRAM SINGH CHOUHAN

Reputation: 65

The approach suggested by @Carcigenicate is correct. Here I will add something to it. The time complexity of code snippet is O(1) i.e. constant time. If I take both range bounds inclusive in nature then it will run exactly for 21 times (6 + 5 + 4 + 3 + 2 + 1). So the return from the method would be n/2^21. So in the bitwise concept, we can say the given number has been right-shifted 21 times if we are considering remainders i.e. n is decimal number.

Upvotes: 0

Carcigenicate
Carcigenicate

Reputation: 45742

If you're considering n to be the argument passed in, note how you say

it (n) does not have an impact on the actual run time of the code.

If n has no impact on the runtime, it wouldn't be O(n^2), since that indicates that the runtime scales (quadratically) with n.

This function looks like it's O(1). The function will always run exactly the same, regardless of input. It will always run exactly 15 times, because n has no bearing on how many times the loop will run. The runtime of the program is decided entirely by the hardcoded arguments given to range, which never change.

Upvotes: 5

Related Questions