This type of algorithm is described as O(log N). Iterative halving of data sets, as described in the binary search example, yields a growth curve that peaks early and slowly levels out as the size of the data sets increases, e.g., a data set of 10 elements takes one second, a data set of 100 elements takes two seconds, and a data set containing 1000 elements takes three seconds. Doubling the size of the input data set has little effect on its growth, as after one iteration of the algorithm, the data set will be halved and, therefore, on par with a data set half its size. This makes algorithms like binary search extremely efficient when working with large data sets.

Such algorithms are called "Divide and Conquer."

In the "binary search" algorithm, we divide the array into two parts at each step.

<< Prev | 10/11 | Next >>
English
Home