9. Space Complexity Given the following implementations of countWays2 and countWays3, what are the space complexities of countWays2 and countWays3 as a function of dist? def countWays2 (dist): count =...

Extracted text: 9. Space Complexity Given the following implementations of countWays2 and countWays3, what are the space complexities of countWays2 and countWays3 as a function of dist? def countWays2 (dist): count = [0] * (dist + 1) count[@] = 1 if dist >= 1: count [1] = 1 if dist >= 2: count[2] = 2 for i in range(3, dist + 1): count[i] = (count[i - 1] + count[i - 2] + count[i - 3]) return count[dist] def countWays3(dist): if dist <= 1:="" return="" 1="" 6.="" if="" dist="=" 2:="" return="" 2="" first="1" second="1" third="2" for="" i="" in="" range(3,="" dist="" +="" 1):="" next_val="third" +="" second="" +="" first="" first="second" second="third" third="next_val" return="" third="" 8.="" pick="" one="" option="" 10="" o="" countways2:="" 0(1),="" countways3:="" o(dist)="" 11="" countways2:="" o(dist),="" countways3:="" o(1)="" 12="" countways2:="" o(dist),="" countways3:="" o(dist)="" 13="" countways2:="" o(2dist),="" countways3:="" o(log(dist))="">