C S 314 Chapter Notes - Chapter 4: Binary Search Algorithm, Linked List, Lookup Table
14 Dec 2016
School
Department
Course
Professor
Document Summary
We can make a sorting routine using merge. Divide and conquer is a technique for solving a large problem by breaking it into two smaller problems, until the problems become easy. If we cut the problem in half each time, the solution will be o(log(n)) or o(n log(n)). If divide-and-conquer cuts the problem in half at each step, the problem size will decrease very fast: by a factor of 1,000 in 10 steps, a factor of. 1,000,000 in 20 steps, a factor of 1,000,000,000 in 30 steps. We soon reach a problem of size 1, which is usually easy to solve. Time will be o(log(n)) if we only process one of the halves, as in binary search. Time will be o(n log(n)) if we process both halves, as in sorting. We can find the midpoint of a list by keeping two pointers, moving one by two steps and another by one step, o(n).
