$\mathcal{O}(n)$, because the loop repeats $n$ times and each iteration takes at most $k$ ms for some $k$, regardless of what $n$ is.

Also $\mathcal{O}(n)$. The reasoning is the same.

In the worst case, we keep calling `f`

until $j-i$ becomes 0. Initially, $j-i$ is $n(1/4-1/5) = 0.05n$, and we keep making $j-i$ smaller by a factor of 2. In total, to get to 0 will take about $\log_2 0.05n$ calls, i.e., we make $\mathcal{O}(\log n)$ calls in total. Each call takes time that doesn't depend on $j-i$, so the runtime is $\mathcal{O}(\log n)$

Here is the outline of the Forward Step of Gaussian Elimination:

```
for each i in 0, 1, 2, ...., m-1
Find the row at i or below with the smallest leading index (Look through n*m entries in the worst case,
which happens if the only non-zero coefficient is in the bottom-right corner)
Swap the rows (Depending on the implementation, could be constant time)
Eliminate all coeffcients below the leading index in the swapped row (at most O(m))
```

This means the Forward Step is $\mathcal{O}(m^2\times n)$.

This was sufficient for full marks, but there is a subtlety there. The subtlety is as follows.

This: Find the row at i or below with the smallest leading index (Look through n*m entries in the worst case, which happens if the only non-zero coefficient is in the bottom-right corner)

is a rough approximation: we can actually find the row at i or below with the smallest leading index in at most $n\times(m-i)$ steps. As it turns out, if you do the math, you'll find that $\mathcal{O}(m^2\times n)$ is a tight bound.

The function is an inefficient implementation of MergeSort (implemented iteratively) in disguise.

`mystery_helper()`

returns the sorted version of `L1+L2`

, in non-increasing order.

`mystery(L)`

returns `L`

, sorted in non-increasing order. This is the iterative implementation of MergeSort: first, we sort lists of length 2 contained in `L`

. Then, we sort lists of length 4 contained in `L`

, and so on, until `L`

is all sorted.

The complexity of `mystery_helper()`

is $\mathcal{O}(n^2)$, so let's say it takes $k n^2$ time

Let's count the runtime by iteration of the `while`

-loop:

```
1-st iteration: k * (n/2) * 2^2 = k*2n
2-nd iteration: k * (n/4) * 4^2 = k*4n
3-rd iteration: k * (n/8) * 8^2 = k*8n
...
log(n)-th iter: k * (2) * n^2 = k*(2n)*n
```

Summing those up, we get $k\times n\times (2+4+8+...+2n)$

Now $2+4+8+...+2n = 2(1+2+4+...+2^{\log_2 n}) = 2(2n-1)$.

That means in total the complexity if $\mathcal{O}(n^2)$.

In [1]:

```
import santa
import copy
def board_full(board):
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == " ":
return False
return True
def invert_board(board):
new_board = copy.deepcopy(board)
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == "X":
new_board[i][j] = "O"
elif board[i][j] == "O":
new_board[i][j] = "X"
return new_board
def o_will_lose(board):
if santa.x_won(board):
return True
if santa.x_won(invert_board(board)):
return False
if board_full(board):
return False
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == " ":
board[i][j] = "O"
if not x_will_win(board):
board[i][j] = " "
return False
board[i][j] = " "
return True
def x_will_win(board):
if santa.x_won(board):
return True
if santa.x_won(invert_board(board)):
return False
if board_full(board):
return False
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == " ":
board[i][j] = "X"
if o_will_lose(board):
board[i][j] = " "
return True
board[i][j] = " "
return False
```

In [2]:

```
print(x_will_win([[" ", "X", " "],
[" ", "X", " "],
[" ", "O","O"]]))
```

In [3]:

```
print(x_will_win([[" ", " ", " "],
[" ", "X", "O"],
[" ", " ", " "]]))
```

In [4]:

```
print(x_will_win([[" ", " ", " "],
[" ", " ", " "],
[" ", " ", " "]]))
```

The contents of `santa.py`

:

In [5]:

```
#1 mark for look-ahead by 1 move
#2 for "don't know" or blank
import copy
def is_row_all_three(board, mark, row_num):
return board[row_num] == [mark] * 3
def is_col_all_three(board, mark, col_num):
for i in range(3):
if board[i][col_num] != mark:
return False
return True
def is_left_diag_all_three(board, mark):
for i in range(3):
if board[i][i] != mark:
return False
return True
def is_right_diag_all_three(board, mark):
for i in range(3):
if board[i][2-i] != mark:
return False
return True
def is_win(board, mark):
for i in range(3):
if is_row_all_three(board, mark, i):
return True
for i in range(3):
if is_col_all_three(board, mark, i):
return True
if is_right_diag_all_three(board, mark):
return True
if is_left_diag_all_three(board, mark):
return True
return False
def make_empty_board():
board = []
for i in range(3):
board.append([" "]*3)
return board
def x_won(board):
return is_win(board, "X")
```