Asymptotic Analysis (Hard)

Question 1

Four Number Sum

Answer 1

Time:
O(n^2) average
O(n^3) worst

Space: O(n^2)

Question 2

SubArray Sort

Answer 2

Time:
O(n)

Space:
O(1)

Question 3

Same BSTs

Answer 3

Time:
O(n^2)

Space:
O(n^2)
(but O(d) is technically possible)

Question 4

Largest Range

Answer 4

Time:
O(n)

Space:
O(n)

Question 5

Min Rewards

Answer 5

Time:
O(n)

Space:
O(n)

Question 6

Zigzag Traverse

Answer 6

Time:
O(n)

Space:
O(n)