Divide and Conquer: Not a strict divide-and-conquer approach.

[lesair]

Shang,

Unfortunately, your "Majority Element Using Divide and Conquer" pseudocode is not a strict divide-and-conquer approach.

The flaw can be found in the call to the "check_candidates()" function. This function will be called on all non-leaf nodes in the recursion tree of the pseudocode, and it will perform counting over segments of the array. The higher the node in the recursion tree, the broader this segment will be, counting and counting again over segments that were previously counted in the calls from the lower nodes in the recursion tree, therefore defeating the divide-and-conquer benefits and ending up with a simple O(n²) time complexity.

In the true divide-and-conquer spirit, you should not be over-counting array segments on each node in the recursion tree.