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?