Definition:Algorithm/Analysis

From ProofWiki
Jump to navigation Jump to search



Definition

There are two primary methods for analyzing algorithms formally:

Correctness

The primary method of validity for algorithms is using a Proof of Correctness.

This is correctness through verification of the algorithm accomplishing its purpose formally, and terminating in $k$ finite steps.


Complexity

The complexity of an algorithm is defined as the number of discrete steps needed to terminate as a function of the number of inputs.


Why not just execute algorithms on machines to find their runtimes?

A common misconception of algorithms is that analyzing run times of algorithmic behaviour using an execution of a finite state machine is just as effective as finding their complexity to demonstrate one algorithm to be more efficient than another. The final step of algorithm design is to implement the algorithm on a machine and not the first step. Algorithm behaviours are very hard to spot in implementation as opposed to when observing complexity. Other factors such as CPU speeds, and physical factors upon machines distort the true runtime on these machines. To compare their implementation speeds is a poor way to generalize algorithm complexity versus proper analysis.

An example of this is Quicksort. Theoretically runs in quadratic time (in worst-case) but, in implementation it might run in logarithmic time depending on implementation (in best-case).


Sources