CORRECTION BELOW
0:00 Explanation
1:58 State the problem
4:20 Introduction to Numbers
9:24 Converting to binary
12:14 Converting to hexadecimal
17:45 Pseudocode
26:41 Prove Correctness (code demo)
35:08 Analyze Time Complexity using Iterative Method
The design and & analysis of an algorithm that converts a base 10 number in N to a base 16 number in N. This video specifically demonstrates a recurrence relation analysis using the iterative method.
Correction to the recurrence relation base case. It should say:
T(n) = T(n/16^k) + k * O(1) ; T(1) = 1
To find the maximum that k reaches (which means the MAX NUMBER OF STEPS),
we set
T(n/16^k) equal to the base case = 1
then solve for k.
Thanks to Aarthi Srinivasan for bringing this up.
Link to formatted answer: imgur.com/qtOcvuZ