Algorithm Design and Analysis

3. From a list of participants ids, find which id is missing from the list. The participant ids sorted in ascendingorder with a certain difference.

Output explanation: the difference for each id is 19, from the list the missing number is 120040 which is after 120021 and before 120059.

a. Design your algorithm in a pseudocode with the complexity of O (lg n) ! (PS: use divide and conquer algorithm)

b. Do analysis for your algorithm resulting in an asymptotic notation!

c. Prove that your algorithm is correct and create your own input / output for 1 case, and minimum number of ids for each case is 10!

\begin{tabular}{|l|l|} \hline \multicolumn{1}{|c|}{ Sample Input } & Sample Output \\ \hline 250002 & 120040 \\ 250021 & \\ 250059 & \\ 250078 & \\ 250097 & \\ 250116 & \\ \hline \end{tabular}