One important thing to note is that for an algorithm to be considered effective, it should take the least time to execute and use the least amount of memory or space. There are different ways of calculating the performance of an algorithm:
Space complexity
In simple terms, whenever a solution to a problem is written, some memory is required to complete it.This is the amount of space required by an algorithm in order to execute. The input determines the space needed for execution- a larger input size means more memory is required.
Components that require space
Instruction space. This is the space required to store the executable version of the program. It is fixed but varies depending on the number of lines of code in the program. It is used to store the compiled version of instructions.
Data space. The space required to store all the constants and variables including temporary variables.
Environment space. The space required to store the environment information needed to resume the suspended function.
Calculating Space Complexity
To calculate space complexity, it is important to know the value of memory used by different types of datatype variables for example; a boolean, character and int8 have 1 byte each while float has 4 bytes.
let d = a+b+c;
console.log(d);
Variables a,b,c and d are integer types hence they will take up 4 bytes each, so the total memory will be (4(4) + 4) where the extra 4 bytes is for the console.log. This is an example of constant space complexity.
An example of Linear Space Complexity is illustrated below.
function sum (a[],n) {
let y= 0;
for(let i=0; i<n; i++) {
y = y + a[i];
}
return y;
}
sum();
In the above example, the space required is 4*n bytes for the array a[] elements. 4 bytes is then required for y,n,i and the return value. The total requirement is
(4n+12)n.
Time complexity
This is the total time required by a program to run until its completion. It is estimated by counting the number of elementary steps performed by an algorithm from start to finish execution.
Time complexity is commonly expressed using the Big O Notation. This is the asymptotic(pertaining values approached at infinity) notation that represents the time complexity. Since an algorithm's performance may change depending on the input, the complexity that is commonly used is Worst-case time complexity. This is the maximum time taken for any input size.
Calculating Time Complexity
There are different types of time complexity.
- Constant Time Complexity
The running time does not change in relation to the input. It is denoted by O(1) where O is Big O. This is the fastest time complexity. It is considered the best case scenario for an algorithm because no matter how big the input size is, it takes the same amount of time to execute.
Example:Array look up
let arr1 = [1,2,4,5];
arr1.index(2);
- Linear Time Complexity
The running time is directly proportional to the input N. Performance grows in direct proportion to the size of the input data set. It is denoted by O(n).
Example
let arr2 = [10,20,30,40,50];
let printValue
for (let i = 0; i < arr2.length; i++) {
let printValue += arr2[i] ;
}
The program has to loop through the array to print each element.
- Quadratic Time Complexity
The running time is directly proportional to the square of the input N. It is denoted by O(n*n) or O(n^2). This is used because the complexity completes both O(1) and O(n).
Example
let text = "";
for(let i = 0; i < N; i++) {
for(let j = 0; j < N; j++) {
text += `The number is ${i} + ${j};`
}
}
- Logarithmic Time Complexity
The running time is proportional to the number of times N can be divided by 2. The working area is divided by 2 with each iteration. It is denoted by O(log n).
Example
function logTime(arr) {
let numberOfLoops = 0
for (let i = 1; i < arr.length; i *= 2) {
numberOfLoops++
}
return numberOfLoops
}
let loop1 = logTime([1, 2, 3, 4]) // 2 loops
From the example above, every time the input length is doubled, the number of operations increases linearly by 1 which makes it half of the input length.
Understanding time and space complexity is important for every developer because it helps one to choose the best case to use for execution and hence ensure that the algorithm is performing at its best state while using the least memory.
Top comments (0)