Algorithmic analysis

We’re interested in several important metrics when analysing the time and space performance of algorithms, expressed with asymptotic notation. These will vary depending on the characteristics of the input parameters.

In particular, for running time, we’re interested in:

• Best case — asymptotically slowest growing case. Usually this isn’t too important because many algorithms can terminate fairly quickly in the best case.
• Worst-case — asymptotically fastest growing case for any input of size $n$, usually what we’re interested in. This gives a guaranteed upper bound on the running time for any input.
  • This is important for real-time applications (like RTOS), when we need a guarantee.
• Average case — often roughly as bad as the worst case. Mean over all possible input cases.
• Expected case — this is the probabilistic equivalent of the average case. Expectation over all possible input costs with respect to a distribution of the input (if uniform, expected is same as average).
• Amortised cost — average cost over a sequence of inputs or operations in the worst case. There are several ways we differently approach this than the others.

Proofs

In the majority of questions, we’ll be asked to prove a worst-case running time for a given algorithm. There are a few approaches we could use to find the running time:

• Model the algorithm’s behaviour as a decision tree. Then, we count how many decisions we need to make, and/or how many leaves there are in the tree.
• Find a closed-form expression in terms of $n$. If $T(n)$ is the worst-case runtime function, and $T(n)\in \Theta (f(n))$, we can find $f(n)$ by:
  • Bottom-up approach — start from $n=0$, work your way up to find a pattern (sometimes difficult).
    • This can be done with induction. We could find a summation, then find a closed form expression of the summation.
  • Top-down approach — start from $n$, and find a recursive expression for $T(n)=n+T(n-1)$ (for example).
    • This is usually the easiest way to prove it. If it’s a recursive algorithm, we can model with a recurrence, then if possible use the master theorem.

Determining a particular case is the worst-case is less rigorous. For our purposes, we can usually get away with making a reasonable assumption for what the worst-case could be.