time complexity of a simple python program

Question

def foo(n):
    for i in range(n):
        for k in range(1,i):
            if k>n/k:
                return k

what is the time complexity of this program? answer says its O(n). any explanations for that would be welcome

edit: typo

Mihai Alexandru-Ionut · Accepted Answer · 2020-01-30 13:22:39Z

3

answer says its O(n).

Yes, the complexity is O(N) because

for k in range(i,i)

for loop is never executed.

So, your code is equivalent to

def foo(n):
    for i in range(n):
       pass

UPDATE

def foo(n):
    for i in range(n):
        for k in range(1,i):
            if k>n/k:
                return k

k>n/k is equivalent to k^2 > n and it's k > sqrt(n)

The main loop is mainly executed sqrt(n) times and the inner loop is executed 0 times, then 1 times, then 2 times, ..... , sqrt(n) times before it returns from the function.

So, the total complexity is O(sqrt(n) * sqrt(n)) which is O(n)

edited Jan 30, 2020 at 13:22

answered Jan 30, 2020 at 11:59

Mihai Alexandru-Ionut

48.6k14 gold badges106 silver badges132 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Serofin Over a year ago

my bad. it was a typo. its (1,i) not (i,i)

Collectives™ on Stack Overflow

time complexity of a simple python program

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related