CSC165 Lecture Week 8

This week the most interesting things that we learned was how to count steps and analyze algorithms. I now know that nesting loops is inefficient. Insertion sort with one nested loop has a worst case time complexity of O(n^2). A maximum slice algorithm with three nested loops has a worst case time complexity of O(n^3). Nesting loops greatly increases the number of steps needed to do something.

I also found it really interesting that for upper bounds you can overestimate them because they're upper bounds. A function is upper bounded by another if it grows no faster than that other function, so if that function happens to grow a lot faster, it doesn't matter because it is still an upper bound. Also, you can underestimate them because they are lower bounds. A function is lower bounded by another function if that other function grows slower than the first one. If the other function grows a lot slower it also doesn't matter because it is still a lower bound.