CSC373H1 Study Guide - Quiz Guide: The Algorithm
Document Summary
I split the array a into 2 sub-arrays. Then we return the complex number that appears more then n. 2a respectively (n here is the length of. 2a ). after that, i will do a linear time equality operation to decide whether those numbers returned by. 3 times in a (here n is the length of a) , and return those numbers which appear more than n. , so h is always an integer if n > 1) // i will use candidates to refer to those numbers in a-left and a-right. If a-left and a-right are empty: return none. Elif a-left and a-right have same candidate : result. add(candidate) Note: getappeartimes(a[1n], candidate) takes an array a and a complex number: candidate, and loop through every complex number in. A, and invoke n comparisons such that compare(a[i], candidate), and keep counting how many times the candidate appears in the array. Induction hypothesis: an array a with n elements function.
