A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.
- Search − Algorithm to search an item in a data structure.
- Sort − Algorithm to sort items in a certain order.
- Insert − Algorithm to insert an item in a data structure.
- Update − Algorithm to update an existing item in a data structure.
- Delete − Algorithm to delete an existing item from a data structure.
- Unambiguous − An algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning.
- Input − An algorithm should have 0 or more well-defined inputs.
- Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output.
- Finiteness − Algorithms must terminate after a finite number of steps.
- Feasibility − Should be feasible with the available resources.
- feasibility = the state or degree of being easily or conveniently done.
- Independent − An algorithm should have step-by-step directions, which should be independent of any programming code.
Algorithm writing is a process and is executed after the problem domain is well-defined. That is, we should know the problem domain, for which we are designing a solution.
An example algorithm that adds 2 values and desplays the result looks like this:
Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP
A minified version of the algorithm that is more commonly used would be:
Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP
THe efficiency of an algorithm can be analyzed at two different stages, before implementation and after implementation. They are the following −
-
A Priori Analysis − This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.
-
A Posterior Analysis − This is an empirical analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.
Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm X are the two main factors, which decide the efficiency of X.
-
Time Factor − Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.
-
Space Factor − Space is measured by counting the maximum memory space required by the algorithm.
The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data.
Time complexity of an algorithm represents the amount of time required by the algorithm to run to completion. Time requirements can be defined as a numerical function T(n), where T(n) can be measured as the number of steps, provided each step consumes constant time.
For example, addition of two n-bit integers takes n steps. Consequently, the total computational time is T(n) = c ∗ n, where c is the time taken for the addition of two bits. Here, we observe that T(n) grows linearly as the input size increases.
Space complexity of an algorithm represents the amount of memory space required by the algorithm in its life cycle. The space required by an algorithm is equal to the sum of the following two components −
-
A fixed part that is the space required to store certain data and variables, that are independent of the size of the problem. For example, simple variables and constants used, program size, etc.
-
A variable part is a space required by variables, whose size depends on the size of the problem. For example, dynamic memory allocation, recursion stack space, etc.
Space complexity S(P) of any algorithm P is S(P) = C + S(I), where C is the fixed part and S(I) is the variable part of the algorithm, which depends on instance characteristic I.
The time complexity of an algorithm is denoted O(· · · ) where the three dots represent some function. Usually, the variable n denotes the input size. For example, if the input is an array of numbers, n will be the size of the array, and if the input is a string, n will be the length of the string.
A common reason why an algorithm is slow is that it contains many loops that go through the input. The more nested loops the algorithm contains, the slower it is. If there are k nested loops, the time complexity is O(nk)[1.1.ref].
For example, the time complexity of the following code is O(n):
for (int i = 1; i <= n; i++) {
// code
}And the time complexity of the following code is O(n^2):
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// code
}
}A time complexity does not tell us the exact number of times the code inside a loop is executed, but it only shows the order of magnitude. In the following examples, the code inside the loop is executed 3n, n + 5 and dn/2e times, but the time complexity of each code is O(n)
for (int i = 1; i <= 3*n; i++) {
// code
}for (int i = 1; i <= n+5; i++) {
// code
}for (int i = 1; i <= n; i += 2) {
// code
}As another example, the time complexity of the following code is O(n^2):
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
// code
}
}If the algorithm consists of consecutive phases, the total time complexity is the largest time complexity of a single phase. The reason for this is that the slowest phase is usually the bottleneck of the code. For example, the following code consists of three phases with time complexities O(n), O(n^2) and O(n). Thus, the total time complexity is O(n^2).
for (int i = 1; i <= n; i++) {
// code
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// code
}
}
for (int i = 1; i <= n; i++) {
// code
}Sometimes the time complexity depends on several factors. In this case, the time complexity formula contains several variables. For example, the time complexity of the following code is O(n*m):
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// code
}
}The time complexity of a recursive function depends on the number of times the function is called and the time complexity of a single call. The total time complexity is the product of these values. For example, consider the following function:
void f(int n) {
if (n == 1) return;
f(n-1);
}The call f(n) causes n function calls, and the time complexity of each call is O(1). Thus, the total time complexity is O(n). As another example, consider the following function:
void g(int n) {
if (n == 1) return;
g(n-1);
g(n-1);
}In this case each function call generates two other calls, except for n = 1. Let us see what happens when g is called with parameter n. The following table shows the function calls produced by this single call:
| function call | number of calls |
|---|---|
| g(n) | 1 |
| g(n-1) | 2 |
| g(n-2) | 4 |
| ... | ... |
| g(1) | 2^(n-1) |
Based on this, the time complexity is
1 + 2 + 4 + · · · + 2^(n−1) = 2^n − 1 = O(2^n)
If you do not understand, take a look at combinatorics.
The following list contains common time complexities of algorithms:
O(1) - The running time of a constant-time algorithm does not depend on the input size. A typical constant-time algorithm is a direct formula that calculates the answer.
O(log n) - A logarithmic algorithm often halves the input size at each step. The running time of such an algorithm is logarithmic, because log2(n) equals the number of times n must be divided by 2 to get 1.
O(sqrt(n)) - A square root algorithm is slower than O(log n) but faster than O(n). A special property of square roots is that sqrt(n) = n/sqrt(n), so the square root sqrt(n) lies, in some sense, in the middle of the input.
O(n) - A linear algorithm goes through the input a constant number of times. This is often the best possible time complexity, because it is usually necessary to access each input element at least once before reporting the answer.
O(n log n) - This time complexity often indicates that the algorithm sorts the input, because the time complexity of efficient sorting algorithms is O(n log n). Another possibility is that the algorithm uses a data structure where each operation takes O(log n) time.
O(n^2) - A quadratic algorithm often contains two nested loops. It is possible to go through all pairs of the input elements in O(n^2) time.
O(n^3) - A cubic algorithm often contains three nested loops. It is possible to go through all triplets of the input elements in O(n^3) time.
O(2^n) - This time complexity often indicates that the algorithm iterates through all subsets of the input elements. For example, the subsets of {1, 2, 3} are the empty set, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} and {1, 2, 3}
O(n!) - This time complexity often indicates that the algorithm iterates through all permutations of the input elements. For example, the permutations of {1, 2, 3} are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) and (3, 2, 1).
An algorithm is polynomial if its time complexity is at most O(n^k) where k is a constant. All the above time complexities except O(2^n) and O(n!) are polynomial. In practice, the constant k is usually small, and therefore a polynomial time complexity roughly means that the algorithm is efficient.
By calculating the time complexity of an algorithm, it is possible to check, before implementing the algorithm, that it is efficient enough for the problem. The starting point for estimations is the fact that a modern computer can perform some hundreds of millions of operations in a second.
For example, assume that the time limit for a problem is one second and the input size is n = 10^5. If the time complexity is O(n^2), the algorithm will perform about (10^5)^2 = 1010 operations. This should take at least some tens of seconds, so the algorithm seems to be too slow for solving the problem. On the other hand, given the input size, we can try to guess the required time complexity of the algorithm that solves the problem.
The following table contains some useful estimates assuming a time limit of one second.
| input time | required time complexity |
|---|---|
| n<=10 | O(n!) |
| n<=20 | O(2^n) |
| n<=500 | O(n^3) |
| n<=5000 | O(n^2) |
| n<=10^6 | O(n log n) or O(n) |
| n is larger | O(1) or O(log n) |
For example, if the input size is n = 105, it is probably expected that the time complexity of the algorithm is O(n) or O(n log n). This information makes it easier to design the algorithm, because it rules out approaches that would yield an algorithm with a worse time complexity.
Still, it is important to remember that a time complexity is only an estimate of efficiency, because it hides the constant factors. For example, an algorithm that runs in O(n) time may perform n/2 or 5n operations. This has an important effect on the actual running time of the algorithm
- [Beginner's guide to C++] (https://www.w3schools.com/CPP/default.asp)
- [Curated list of algorithms] (https://www.geeksforgeeks.org/fundamentals-of-algorithms/?ref=shm)