Understanding Program Efficiency, Part 2
In this unit we continue our exploration of abstraction with respect to algorithm complexity. This lecture discusses the classification of algorithms according to how the performance of an algorithm grows relative to the size of the problem or task the algorithm solves or performs. Algorithms are classified by average run-time complexity, defined as the average number of steps the algorithm takes for a problem of size 'n'. Abstraction ignores the implementation of the algorithm and only considers the growth in the number of (primitive) steps an algorithm takes as the size of the problem grows. The video lecture introduces big 'O' notation and gives examples for linear, log, quadratic, and exponential complexity. The lecturer states that exponential complexity should be avoided in general. Although the examples are in C++, the same principles apply to algorithms in general, regardless of language.
Source: Ana Bell, https://www.youtube.com/watch?v=0jljZRnHwOI
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.