Solution: Nested Loop with Multiplication (Pro)

Solution #

The outer loop in the main function has $n$ iterations as it iterates on the list generated from range(n). If the condition j < var is true, the inner loop is entered. However, immediately, j is doubled. Note that j is not reset to $1$ in the code. The inner while loop will run at most once for each iteration of the outer loop. Therefore, lines 6, 7 and 8 run $O(n)$ times each. Since we are interested in an upper bound on the worst case running time, let’s assume these statements run exactly ...