CODEWITHSUNDEEP
pythonalgorithmpython-3.xbig-o
suugarpie
suugarpie

Reputation: 31

Run time of nested while loops

To find the number of iterations of the inner while loop, is it the same as finding the run time of inner loop? Also since, the inner loop is dependent on on the outer loop,I know I should multiply the number of times the inner while loop runs with the outer while loop to get the number of times it is iterated, right? I'm kind of confused on how to calculate # of iterations for while loops. Any help would be appreciated. Thanks!

def nested(n):
    b = 1 
    while b <= n:
        i = 1
        while i < b:
            print(i)
            i = i*3
        b += 1

Thanks everyone for all the help!

I think I understand what the answer is. So, since we're trying to find the number of times the inner loop iterates (which is n-1), I also need to consider the # of times the outer loop iterates of the inner loop (which is n). Therefore, we'll iterate the inner loop (n-1), n times, thus giving us (n(n-1))/2 if we use summation notation. Hopefully that's right.

Upvotes: 3

Views: 2588

Answers (3)

amit
amit

Reputation: 178431

Time complexity is O(nlogn) (and this is the number of times the inner loop repeats itself).

Outer loop runs n times. For the bth iteration of the outer loop, the inner loop runs log_3(n-b) times.

Summing it together we get:

T(n) = sum{log_3(n-b) | for b=1 to b=n}
T(n) = log_3(n) + log_3(n-1) + log_3(n-2) + ... + log_3(1) =
T(n) = log_3(n * (n-1) * (n-2) * .... * 1) = log_3(n!)

And since log(n!) is in Theta(nlogn), this is your time complexity.

Upvotes: 1

Dolev
Dolev

Reputation: 684

The short answer is: sum{i=1; i<=n ;i++} log3(i) = log3(n!)

Upvotes: 1

Matthew Cole
Matthew Cole

Reputation: 597

You've got a two questions, so I've broken them apart.

To find the number of iterations of the inner while loop, is it the same as finding the run time of inner loop?

No. I've taken the liberty to modify your code a bit to use time.process_time to measure run time without interference from the operating system's scheduler, and to eliminate your interior print statement (I/O calls are deceptively expensive).

import time

def nested(n):
    loops = list()

    #Start outer timer
    func_start = time.process_time()

    b = 1 
    while b <= n:

        #Start loop timer
        loop_start = time.process_time()

        i = 1
        while i < b:
            #print(i)
            i = i*3
        b += 1

        #Finish loop timer
        loop_finish = time.process_time()
        loops.append(loop_finish - loop_start)

    #Finish outer timer
    func_finish = time.process_time()

Then I add a logging statement:

print("Function time: %f, Sum loop times: %f, iterations: %i, iterations by runtime: %.0f" 
        % (func_finish - func_start, 
            sum(loops), 
            len(loops), 
            (func_finish - func_start) / (sum(loops)/len(loops)))  )

Finally, I run it a few times. Here are the results:

Function time: 0.000019, Sum loop times: 0.000010, iterations: 10, iterations by runtime: 19
Function time: 0.000135, Sum loop times: 0.000102, iterations: 100, iterations by runtime: 132
Function time: 0.001461, Sum loop times: 0.000875, iterations: 1000, iterations by runtime: 1670
Function time: 0.017174, Sum loop times: 0.011532, iterations: 10000, iterations by runtime: 14892
Function time: 0.193567, Sum loop times: 0.133996, iterations: 100000, iterations by runtime: 144457

As you can see, as the number of iterations increases, using relative run times to try to estimate the number of iterations becomes less accurate.

Also since, the inner loop is dependent on on the outer loop,I know I should multiply the number of times the inner while loop runs with the outer while loop to get the number of times it is iterated, right?

This is true for theoretical applications. If I have n instructions in an inner loop, and the inner loop is run m times, I'd predict that the total run time is in fact, mn. However, you have to keep in mind that a line of code does not equal a single instruction. In fact, even some instructions don't equal other instructions in terms of execution time (floating point arithmetic versus integer arithmetic, for example). We saw that in our timed example.

For purposes of calculating Big-O runtime bounds, the technique you suggest for multiplying inner loop statement counts by number of loops works. In the real world, it gets more complicated, and doubly so for interpreted languages like Python.

Upvotes: 3

Related Questions