CODEWITHSUNDEEP
pythontime-complexity
Serofin
Serofin

Reputation: 57

time complexity of a simple python program

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

Upvotes: 1

Views: 97

Answers (1)

Mihai Alexandru-Ionut
Mihai Alexandru-Ionut

Reputation: 48337

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)

Upvotes: 3

Related Questions