For this problem set, you will be presented a number of recurrence relations and asked to state their actual time complexity, showing your work in the process.
Problems:
1. T(N) = 3T(N/3) + O(N)
2. T(N) = 3T(2N/3) + O(1)
- This is the recurrence relation for the "stooge sort" algorithm, a deliberately poor-performance sort.
3. T(N) = 4T(N/2) + O(N)
4. T(N) = 2T(N/2) + O(N log(N))
Will give a good review with answer with a good explanation!