Embercode: AI-powered software engineer course

1. The find_median search for two sorted lists of m and n values, as written in the lesson, runs in which time?

O(m + n), because the lists are merged firstO(min(m, n) * log(min(m, n)))O(m * n)O(log(min(m, n)))

2. The lesson's Strassen recurrence is T(n) = 7 T(n/2) + n squared. Which growth rate does it give?

O(n^2.807)O(n^2)O(n^3)O(n^2.5)

3. What does this program print? ``

python
a = [2, 4, 6]
b = [1, 3, 5, 7]
m = len(a)
n = len(b)
half = (m + n + 1) // 2
i = 1
j = half - i
print(f'half={half} i={i} j={j} aLeft={a[i - 1]} bRight={b[j]}')
c = [1, 2, 3, 4]
d = [5, 6, 7, 8, 9]
print(f'half={(len(c) + len(d) + 1) // 2} total={len(c) + len(d)}')

``

half=3 i=1 j=2 aLeft=2 bRight=5 half=5 total=9half=4 i=1 j=3 aLeft=4 bRight=5 half=5 total=9half=4 i=1 j=3 aLeft=2 bRight=7 half=4 total=9half=4 i=1 j=3 aLeft=2 bRight=7 half=5 total=9

4. What does this program print? ``

python
def naive(a, b):
    n = len(a)
    c = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            for j in range(n):
                c[i][j] += a[i][k] * b[k][j]
    return c


a = [[1, 0], [2, 1]]
b = [[3, 1], [0, 2]]
print(naive(a, b))
x = [[2, 1], [0, 3]]
y = [[1, 4], [2, 5]]
print(naive(x, y))

``

[[3, 2], [6, 4]] [[4, 13], [6, 15]][[3, 1], [0, 4]] [[4, 13], [6, 15]][[3, 1], [6, 4]] [[4, 13], [6, 15]][[3, 1], [6, 4]] [[4, 13], [7, 15]]

5. Why does find_median compute half as (m + n + 1) // 2 instead of (m + n) // 2?

It makes the search run one step fewerIt puts the extra value on the left when the total is odd, so the largest left value is the medianIt keeps the result from being a float when m + n is oddIt puts the extra value on the right when the total is odd, so the smallest right value is the median

Median and matrices in Python