W2D4 - Big-Oh Notation
Topics
Big-Oh Notation
Simplicity: O(2n+4) == O(n)
Dominant Family: O(1) + O(n!) == O(n!)
Treat as families/categories of functions
Deals with worst case scenario / upper bound
O(g) { f | c*f does not dominate g} for some constant c -- belongs in the set of functions
Time Complexity
Space Complexity
Asymptotic Analysis - describe behavior of a function as it approaches infinity
Asymptotic != Amortization
RAM Model of Computation
Assumes we're running our algorithm on a hypothetical Random Access Machine, where data/processing can get infinitely large
Moore's Law - observation/projection that estimates that the number of transistors in a dense integrated circuit doubles approiximately every two years
XOR - Exclusive Or, written as ^ in Ruby. Can do some cool math - [1,2,3] xor-ing 0000 by 1 (0001), 2 (0010), and 3 (0011) would result in identity again
Assessment2 - Took Practice Assessment this morning, 1 hour to work through their RSpecs to write a Blackjack game. Finished with a few minutes to spare, focused on reading/fulfilling RSpecs
Projects
Execution Time Differences/Algorithms
my_min(list) - O(n^2) & O(n) versions
largest_contiguous_subsum(arr) - O(n^2) & O(n) versions
Anagrams
first_anagram?(string1, string2) - O(n!), permutation
second_anagram?(string1, string2) - O(n^2), nested loops
third_anagram?(string1, string2) - O(nlogn), quick-sort 2 arrays
fourth_anagram?(string1, string2) - O(n), 2 hashes
fifth_anagram?(string1, string2) - O(n), 1 hash
Two sum Problem
bad_two_sum?(arr, target_sum) - O(n^2), nested loops
okay_two_sum?(arr, target_sum) - O(nlogn), binary search
great_two_sum?(arr, target_sum) - O(n), 1 hash
Windowed max range
max_windowed_range(array, window_size) - O(n + 2w), expensive to run through window twice to calculate max/min in every window
O(n) time using a MaxMinQueStack
MaxMinQueueStack - create a MyStack class that tracks max & min using @max_array & @min_array. In a new QueueStack class
Initialize - [MyStack1, MyStack2]
Enqueue - Mystack1.push(el)
Dequeue - take all elements from MyStack1, push to MyStack2 (should flip stack, like a slinky) then Mystack2.dequeue. If no elements on MyStack1, then dequeueing will run in O(1) time since know exactly where element is. Amortized time is constant
Max/Min - track within QueueStack, similar way to how we tracked in MyStack
Partner: Sarah Fuchs
Learnings
Algorithms are fun!!!!
Big-Oh Notation is like extremely hand-wavy math that rounds a lot
Merge Sort - runs in O(nlogn) time because each level of the process will require:
T(n) = O(1) + 2T(n/2) + O(n) time per level
log(n) + 1 distinct levels
O(n) * O(logn) = O(nlogn) time complexity
Quick Sort - O(nlogn) average worst case time complexity
Worst case - O(n^2) if always choose the smallest object
Practically, often more efficient to use middle element as pivot rather than first element, in case array has been sorted (correct direction or opposite)
Bubble Sort - worst case scenario is O(n^2)
Binary Search - O(logn), worst case scenario is O(n^2)
