Fast power and Hanoi

Questions 1 to 5 of 8

1. 1. Write the Big-O for the number of multiplications that fast(x, n) does, using n for the exponent.

   Type your answer.

2. 2. What is the time complexity of printing every move for an n-disk tower?

   O(n)O(n^2)O(2^n)O(log n)
3. 3. What is the second line printed by this program? ``python def iterative(x, n): result = 1 base = x e = n while e > 0: if (e & 1) == 1: result = result * base base = base * base e = e >> 1 return result print(f"iterative(2, 6) = {iterative(2, 6)}") print(f"iterative(3, 5) = {iterative(3, 5)}") ``

   iterative(3, 5) = 243iterative(3, 5) = 81iterative(3, 5) = 125iterative(3, 5) = 729
4. 4. What is the second line printed by this program? ``python def solve(n, source, target, spare): if n == 0: return solve(n - 1, source, spare, target) print(f"Move disk {n} from {source} to {target}") solve(n - 1, spare, target, source) solve(2, "A", "B", "C") ``

   Move disk 2 from A to CMove disk 2 from A to BMove disk 1 from A to BMove disk 2 from C to B
5. 5. In the Hanoi function, the first recursive call sends the top n - 1 disks to the ____ peg.

   Type your answer.