w2d4
More new material today with little time to digest yesterday’s! We discussed time complexity of algorithms today. Time complexity (represented mathematically as big O) describes the worst case runtime of an algorithm (independent of external factors such as computer hardware, compiler speed, etc.) in the form of mathematical functions such as ln(n), n^2, and so on.
The running times in functions in order from fastest to slowest are O(1), O(ln(n)), O(n), O(n*ln(n)), O(n^2), O(2^n), and O(n!). They can typically be determined by dissecting an algorithm or function and determining how many iterations, loops, or operations are occurring. They can also be determined by getting data points on runtime for varying numbers of elements.
Finally, we ended by doing some cool demos involving running benchmarks for bubble sort and merge sort on 1000, 3000, 4000, and 5000 elements, which showed that bubble sort was really slow (at least for large number of elements as it is pretty fast for smaller numbers of elements). While this lecture was interesting, I found many aspects of it confusing, like average case and amortized time. I guess that’s what I’ll be reading about this weekend! The rest of the day involved writing various functions, determining their time complexities, and then optimizing to decrease big O, including some cool implementations such as a MinMaxStackQueue to keep track of maxs/mins instantaneously in constant time while moving through different numbers instead of having to calculate the maxs/mins during every iteration of different numbers. This was very hard, as we created our own data structures to do this. Again, we barely had time to get to the last step (which still wasn’t working at the time of this writing so another thing to work on during the weekend :/).
Straight from bigocheatsheet.com is this graph below for a more visual depiction of the various big Os discussed in this post.