What is an Algorithm?
A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.
Algorithm Links
Properties of Algorithms
- Input - An algorithm has input values from a specified set.
- Output - From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem.
- Definiteness - The steps of an algorithm must be defined precisely.
- Correctness - An algorithm should produce the correct output values for each set of input values.
- Finiteness - An algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set.
- Effectiveness - It must be possible to perform each step of an algorithm exactly and in a finite amount of time.
- Generality - The procedure should be applicable for all problems of the desired form, not just for a particular set of input values
Measuring Algorithms
- Algorithm times measured in terms of growth of an algorithm
- Algorithm times written in Big-O Notation
Vocabulary/Terms
Asymptotic Notations
Asymptotic Notations are languages that allow us to analyze an algorithm’s running time by identifying its behavior as the input size for the algorithm increases (aka an algorithm’s growth rate)
- Does the algorithm suddenly become incredibly slow when the input size grows?
- Does it mostly maintain its quick run time as the input size increases?
Types of Asymptotic Notations
- Big-O Notation (O-notation): worst-case
- Omega Notation (Ω-notation): best-case
- Theta Notation (Θ-notation): average-case
Time and Space Complexity
Space Complexity
Space complexity is a measure of how efficient your code is in terms of memory used. Space complexity analysis happens almost in the same way time complexity analysis happens.
For example, consider the following code :
vector<int> V;
for (int i = 0; i < N; i++) V.push_back(i);
The code snippet ends up creating a vector of size N. So, space complexity of the code is O(N).
Additional space / memory is measured in terms of the largest memory use by the program when it runs. That is to say, if you allocated O(N) memory, and later free it, that does not make the space complexity of your program O(1).