Notes > Computation and Algorithms > Algorithm Analysis and Pseudocode
Algorithm analysis allows us to compare algorithms. The factors involved in this comparison are efficiency and running time which are linked to each other. The running time of an algorithm will typically change depending on the size of input.
Algorithms have a best case, average case, and worse case running time. The worst case running time is the longest possible time it could take for the algorithm to terminate. The best case is the opposite of this. The average case attempts to estimate the average time that the algorithm will take given a certain size of input but this can be quite difficult to calculate.
The actual running time of an algorithm can be measured by taking time measurements using a function such as System.currentTimeMillis() in Java at the beginning and end of the algorithm execution.
Running time can be estimated in a more general manner by using Pseudocode to represent the algorithm as a set of fundamental operations which can then be counted. Pseudocode gives a high-level description of an algorithm without the ambiguity associated with plain text but also without the need to know the syntax of a particular programming language.
Pseudocode contains all of the following features:
- Conventional loops:
- If... then... else...
- While... do...
- Repeat... until...
- For... do...
- Indentation is used instead of parentheses (brackets)
- Method declaration:
- Method name: Algorithm methodName(args)
- Input description: Input...
- Output description: Output...
- Method calls: var.methodName(args)
- Return values: return...
- Assignment: <--
- Equality comparison: =
In a pseudocode description of an algorithm, each line can be viewed as a certain numer of operations which can be counted and added up to find a total value for the algorithm. Some examples are shown below:
- varNumber <-- X
(2 operations - 1 array value retrieval, 1 assignment)
- For a <-- 1 to n do...
(n operations - any operations within this loop will then be multiplied by n also as they will be carried out n times)
- return varNumber
Search for "Algorithm Analysis and Pseudocode" on:
eBay (UK) |
Search for "Algorithm Analysis and Pseudocode" on the rest of Computing Students: Algorithm Analysis and Pseudocode