0
def g(n):
    s = 0 
    for i in range(n):

        # min(a,b) returns the smaller value of a and b 
        for j in range(min(100,i)): 
            s = s + 1
    return s

As stated in the title, "How do I derive that the time complexity of function g(n) is O(n)?"

Like it seems to me that the double for loop will let the time complexity be closer to O(n2) instead of O(n)?

To be more specific, this was my thought process (with reference to the inner for-loop):

for j in range(min(100,i)):
  • For large values of n (n >> 100), it seems to me that its reasonable to state that the time complexity is O(n)

  • While for values of n (n < 100), it seems to me that O(n2) time complexity will make more sense

Is this line of reasoning correct?

0

1 Answer 1

1

The inner loop is bounded by a constant so the running time of the whole thing is O(n).

Briefly the definition of the Big-O is that for large n's some function f(n) is O(g(n)) if there exists a constant k such that f(n) ≤ k * g(n). In this case since the inner loop will run at most 100 times the time the program takes to run grows with n as something like f(n) = 100*n + m where m is some constant. Thus we can see that the running time of this program is O(n) because 100*n + m grows like just 100*n if n is large relative to m and 100*n will always be less than k*n if k is some constant greater than 100.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.