Algorithms

What is an Algorithm?

• An algorithm is a set of instructions for accomplishing a task
• Any piece of code can be treated as an algorithm

Binary Search

• Input: accepts a sorted list of elements
• If the element you're looking for is in the list, then the position of the element is returned
• Starts by finding the middle of the list, adjusting the low or high of the list, and repeating until a match is found

Logarithms

• The flip of exponentials
• 2^3 = 8 --> log(2) 8 = 3 (hint: How many 2s do I multiply to get 8?)

Big O Notation

• Special notation that tells you how fast an algorithm is
• Not represented in seconds, rather a comparison of the number of operations
• It tells you how fast an algorithm grows --> how quickly the run time increases as input increases
• Algorithm times are expressed in Big O Notation
• Establishes a worst-case run time --> simple search (searching through all items) will not be slower than O(n)

O(n) --> n represents number of operations

Common Big O Run Times

1. O(log n): log time --> Binary Search
2. O(n): linear time --> Simple Search
3. O(n * log n) --> fast sorting algorithm, like quick sort
4. O(n^2) --> slow sorting algorithm, like selection sort
5. O(n!): factorial time --> a really slow algorithm, like a traveling salesperson

Traveling Salesperson

• An exponential increase in permutations as input (number of cities) increases when trying to determine most efficient course of travel
• As input exceeds 100, this algorithm type is ineffective
• Unsolved problem in computer science --> impossible to have a smart solution to algorithm for this problem

Source:

Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People by Aditya Y. Bhargava