Execution time of nested loops
To find the number of iterations of the inner while loop, is it the same as finding the execution time of the inner loop? Also, since the inner loop depends on the outer loop, I know that I have to multiply the number of times the inner while loop works with the outer while loop to get the number of repetitions, right? I'm a little confused about how to calculate # of iterations for while loops. Any help would be greatly appreciated. Thank!
def nested(n):
b = 1
while b <= n:
i = 1
while i < b:
print(i)
i = i*3
b += 1
Thanks everyone for the help!
I think I understand what the answer is. Thus, since we are trying to find the number of times the inner loop has iterated (which is n-1), I also need to consider the number of times the outer loop has iterated (which is n). So we'll iterate over the inner loop (n-1), n times, which gives us (n (n-1)) / 2 if we use the summation notation. Hope this is correct.
source to share
You have two questions, so I have broken them down into parts.
To find the number of iterations of the inner while loop, is it the same as finding the execution time of the inner loop?
Not. I took the liberty of modifying the code a bit to use time.process_time to measure execution time without interference from the operating system scheduler and to eliminate your inner statement print
(I / O calls are deceivingly 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 registration 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 several 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 execution time to try to estimate the number of iterations becomes less accurate.
Also, the inner loop depends on the outer loop, I know that I have to multiply the number of times the inner while loop works with the outer while loop to get the number of repetitions, right?
This is true for theoretical applications. If I have n instructions in an inner loop, and the inner loop is executed m times, I would predict that the total execution time is, in fact, mn. However, you should keep in mind that a line of code is not equal to one command. In fact, even some instructions are not equal to other instructions in terms of runtime (for example, floating point arithmetic and integer arithmetic). We saw this in our temporary example.
For the purpose of calculating Big-O runtime bounds, the method you propose to multiply the inner loop expression by the number of loops works. In the real world, it becomes more complex and doubly suited for interpreted languages like Python.
source to share
Time complexity O(nlogn)
(and this is the number of repetitions of the inner loop).
Outer loop starts n
times. For the b
th iteration of the outer loop, the inner loop starts log_3(n-b)
once.
Summarizing this 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 it log(n!)
is in Theta(nlogn)
, this is your time complexity.
source to share