Embercode: AI-powered software engineer course

1. For T(n) = T(n/2) + n, the number of levels is log base ____ of n.

Type your answer.

2. For T(n) = 2 T(n - 1) + 1, the total work is 2 to the power n minus 1, which is ____ growth.

Type your answer.

3. For T(n) = 2 T(n - 1) + 1, which statements about the recursion tree are correct?

Pick every answer that is true.

Level k has 2 to the power k nodesThe depth of the tree is log2(n)For n = 10 the total work is 1023The total is O(n), because each node does 1 unit of work

4. For T(n) = T(n/2) + n with n = 1024, which statements are correct?

Pick every answer that is true.

The level totals are 1024, 512, 256 and so onThe total work is 2046The work per level grows at each level going downThe growth rate is O(n)

5. What does this code print? ``

python
def level_totals(n, children, cost):
    totals = []
    level = [n]
    while level:
        totals.append(sum(cost(s) for s in level))
        nxt = []
        for s in level:
            nxt.extend(children(s))
        level = nxt
    return totals

kids = lambda s: [s - 2, s - 2] if s > 1 else []
cost = lambda s: s if s > 1 else 0
totals = level_totals(7, kids, cost)
print(totals, sum(totals))

``

[7, 10, 12] 29[7, 10, 12, 0] 29[7, 10, 12, 0, 0] 29[7, 5, 3] 15

Recurrence trees