CISC 121 Lecture Notes - Lecture 26: Binary Search Algorithm, Linear Search, Binary Logarithm

• School: Queen's University
• Department: Computing
• Course: CISC 121
• Professor: Wendy L Powley

Document Summary

If we were to attach mathematical formulas to the line and curve on that chart, we would get y = mx for the linear search, where m is the line"s slope. Time taken increaeses as the number of items being searched increases, but the slope is decreasing. This is due to a doubling of the number of items only increasing the running time by a single time unit. If you"re not mathematically inclined, you may find your eyes glaze over at the mentions of logarithms, but the essential principle is fairly simple. Asking what logb(n) is for any two natural numbers, b and n, is the same as asking, how many times does one have to multiply b by itself to reach or exceed n? . Note: b was chosedn as the name for this number, as the number is called the base. We humans are comfortable using base value 10. We call our base 10 numbering system decimal.