WEEK 4

WEEK 4(Assighment) 1. Referring back to question 1 in the assignment, identify the correct formulation of the product of two complex numbers a+bi and c+di using only three real multiplications. O (a+b)(c+d)-bd-ac+i[ac-bd] O (a+c)(b+d)-cd-abrifab-cd] O ab-cdti[(a+c)(b+d)-bc-ab] @® ac-bd+il(a+b)(c+d)-bd-ac] @ Correct 2. Referring back to question 2a in the assignment, given the modified version of the closest pair of points algorithm, identify the best asymptotic running time you can get for this algorithm. O O(logs(n)) @® O(nlog(n)) O o(n?) O O(logi(n)) @ Correct 3. Referring back to question 2b in the assignment, given the modified version of the closest pair of points algorithm, identify the highest asymptotic lower bounds for this algorithm from the following list: 4. Referring back to question 3 in the assignment, explain why your algorithm only requires at most O(log(n)) queries to locate the median. O The number of queries cannot be O(log(n)) because the SELECT algorithm requires time complexity O(n2). O The algorithm separates the data into two roughly equally sized sets with each recursive call and finds the median of each of these sets. @ The algorithm eliminates roughly half the data with each recursive call. @ Correct