Source: https://docs.google.com/presentation/d/1NSRRSnpVVfveALvv-_tfbTfB9wiLaXEaVb93Cy2ZUfE/edit#slide=id.p
Complexity
Measuring efficiency (how long it takes your program to run)
Algorithmic Complexity
Algorithmic complexity is a very important topic in computer science. Knowing
the complexity of algorithms allows you to answer questions such as:
- How long will a program run on an input?
- How much space will it take?
- Is the problem even solvable?
- What data structure (ADT) to choose.
Complexity
- How well a computer algorithm scales as the amount of data increases.
- We need a way to compare algorithms. So we will learn how to create special
categories (runtime classes), add algorithms to these categories and
compare them instead.
Running Time
- Best case: the last amount of time possible
- Worst case: the most amount of time possible
- Average case
Time Complexity
A way of showing how the runtime of function increases as the size of the
input increases
Time: Comparing Implementations
Implementations of the same functional abstraction can require different
resources
Comparing Orders of Growth
Properties of Orders of Growth
- Constants: Constant terms do not affect the order of growth of a process.
- Logarithms: The base of a logarithm does not affect the order of growth of a
process.- Lower-order terms: The fastest-growing part of the computation dominates the
total.