Computer Science is a relatively new science. Most of it originates from the 20th century.
However, the Divide and Conquer principle is ancient (’Divide ut regnes’ or ‘Divide et impera’). Often associated with Ceaser, Machiavelli, and Napoleon.
The principle is quite simple:
One of the most famous Divide and Conquer algorithms is Merge Sort. Other examples are binary search (no need to combine there), etc.
We also need to prove the correctness/run time of these algorithms, for example, by proof of induction (formal proof) or repeated unfolding (informal proof).
Take, for example, the following algorithm:
What is the worst-case time complexity?
Because of line 4, the time complexity is $\text{O}(n\log n)$. The while loop will make $k$ divisions, such that $k=\log_3(n)$. I.e., $3^k=n$. As a result, $k=\text{O}(\log(n))$.
