CODEWITHSUNDEEP
python
user5514593
user5514593

Reputation:

Time complexity of a python program with nested loops

This is regarding finding the time complexity of a python program which involves nested loops.

def Function(n):
    count = 0
    for i in range(n / 2, n):
        j = 1
        while j + n / 2 <= n:
            k = 1
            while k <= n:
                count = count + 1
                k = k * 2
            j = j + 1

    print (count)

Function(20)

I'm trying to find out the complexity but little confused with the arguments in range function and so much of nested loops. I got stuck while finding the time complexity of the second loops and the inner most.]

Upvotes: 0

Views: 1410

Answers (1)

Amit Upadhyay
Amit Upadhyay

Reputation: 7401

okay, let us begin with the inner while loop, we can clearly see that this condition holds true only when 2 * 2 * 2 * 2 * ... k times <= n i.e 2^k <= n for calculating the time complexity we can say

2^k = n

taking log base 2 both side we get k = log2 (n) so we can say that the inner loop executes log2 (n) times.

Coming to the middle loop which has again a constrain j+n/2 <= n, and j is being incremented by 1 each time this loop is running. So if you think a little bit you can say that it will execute n/2 times.

And coming to the outer loop you can directly see the range(n/2, n) which I think gives you idea about the execution of that loop. i.e n/2 times again. So overall time complexity is O((n/2) * (n/2) * log2 (n)) which you can say is O(n^2 log2 (n))

below I have edited your program with the comments in it.

def Function(n):
    count = 0
    for i in range(n / 2, n):  # Outer loop execute n/2 times
        j = 1
        while j + n / 2 <= n:  # Middle loop executes n/2 times
            k = 1
            while k <= n:  # Inner loop execute logn times
                count = count + 1
                k = k * 2
            j = j + 1

    print (count)

Function(20)

you can watch some videos on youtube which will teach you to find the time complexity of programs.

Upvotes: 2

Related Questions