$\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)$.
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
print(x_will_win([[" ", "X", " "],
[" ", "X", " "],
[" ", "O","O"]]))
print(x_will_win([[" ", " ", " "],
[" ", "X", "O"],
[" ", " ", " "]]))
print(x_will_win([[" ", " ", " "],
[" ", " ", " "],
[" ", " ", " "]]))
The contents of santa.py:
#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")