An algorithm is a set of well-defined instructions for solving a specific
problem. A problems can be solved in various ways so algorithm for same problem
may differ. Because there are various ways to solve a problem, there must be a
way to evaluate these solutions or algorithms in terms of performance and
efficiency.
What is Big O Notation ?
Big O Notation is a metric for determining the efficiency of an algorithm. It
allows you to estimate how long your code will run on different sets of inputs
and measure how effectively your code scales as the size of your input
increases.
Big O Notation is a metric for determining the efficiency of an algorithm. It
allows you to estimate how long your code will run on different sets of inputs
and measure how effectively your code scales as the size of your input
increases.
Big O notation measures the efficiency and performance of your algorithm using
time and space complexity.
What is Time and Space Complexity?
An algorithm's time complexity specifies how long it will take to execute an
algorithm as a function of its input size. Similarly, an algorithm's space
complexity specifies the total amount of space or memory required to execute an
algorithm as a function of the size of the input.
Lets consider problem of finding factorial of given number i.e. input.
If input is 4 it will calculate 4*3*2*1 and output 24.if your input is 5,
it will output 120 (meaning 5*4*3*2*1).
const GetFactorial = (input) => {
let factorial = 1;
for (let i = 0; i <= input; i++) {
factorial *= i;
}
return factorial;
};
In the code above, we have three statements:
statement 1 --> let factorial = 1;
statement 2 --> factorial *= i;
statement 3 --> return factorial;
because there is a loop, the second statement will be executed based on the
input size, so if the input is four, the second statement (statement 2) will be
executed four times, meaning the entire algorithm will run six (4 + 2) times.
In plain terms, the algorithm will run input + 2 times, where input can be any
number. So the time complexity of our factorial program is O(n), where n =
number specifiying i put size.
In Big O, there are six major types of complexities (time and space):
1) Constant: O(1)
2) Linear time: O(n)
3) Logarithmic time: O(log n)
4) Quadratic time: O(n^2)
5) Exponential time: O(2^n)
6) Factorial time: O(n!)
7) Log linear time:O(n * log n)
8) Cubic time:O(n^3)
Comparing Algorithm Complexity:
1) O(1) - Excellent/Best
2) O(log n) - Good
3) O(n) - Fair
4) O(n log n) - Bad
5) O(n^2), O(2^n) and O(n!) - Horrible/Worst
How to calculate time complexity ?
1) When your calculation is not dependent on the input size, it is a constant
time complexity (O(1)).
2) When the input size is reduced by half, maybe when iterating, handling
recursion, or whatsoever, it is a logarithmic time complexity (O(log n)).
3) When you have a single loop within your algorithm, it is linear time
complexity (O(n)).
4) When you have nested loops within your algorithm, meaning a loop in a loop,
it is quadratic time complexity (O(n^2)).
5) When the growth rate doubles with each addition to the input, it is
exponential time complexity (O2^n).
Big O Time Complexity Examples:
Constant Time: O(1):
When your algorithm is not dependent on the input size n, it is said to have a
constant time complexity with order O(1). This means that the run time will
always be the same regardless of the input size.
For example:
function getLastElement(array)
{
return array[array.length -1];
}
let arr = [78, 45, 12, 40, 10];
console.log(getLastElement(arr)); // 10
In above code the function getLastElement() require only one execution step
irrespective of size of input array,in sense even if size of input array is
increased or decreased then also it will complete in only one execution step.
This means the function getLastElement() has constant time with time complexity O(1).
Another way to write a code:
function getLastElementBad(array)
{
for (let i = 0; i < array.length; i++) {
return array[array.length -1];
}
}
let arr = [78, 45, 12, 40, 10];
console.log(getLastElementBad(arr)); // 10
This code is not so good as it is unnessarily looping over input array. w.r.t.
this code the function always returns the last element of the array, regardless
of the size of the input array. The loop runs only once, so the time complexity
is constant.
This means the function getLastElementBad() has constant time with time
complexity O(1).
Linear Time: O(n):
You get linear time complexity when the running time of an algorithm increases
linearly with the size of the input.
For example
if an algorithm is to return the factorial of any inputted number. This means if
you input 5 then you are to loop through and multiply 1 by 2 by 3 by 4 and by 5
and then output 120:
function getFactorial(n)
{
let factorial = 1;
for (let i = 2; i <= n; i++) {
factorial = factorial * i;
}
return factorial;
};
console.log(getFactorial(5)); // 120
According to calculation time complexity of this getFactorial() function seems
to be O(n) +2.But in the context of Big O notation, constants and lower-order
terms are typically ignored because they don't significantly affect the overall
growth rate of the function as the input size approaches infinity.
In the case of your getFactorial function, there's a constant-time operation
(factorial = factorial * i;) inside the loop, which is executed n times.
However, the "+2" mentioned referring to the two operations:
let factorial = 1; and the initialization of i in the loop return factorial;
returning result
are considered constant-time operations that do not depend on the input size.
Thus, they are not included in the Big O notation.
So, even if we technically count those two additional operations, the dominant
factor still comes from the loop that runs n times, making the time complexity
O(n).
Logarithm Time: O(log n):
This is similar to linear time complexity, except that the runtime does not
depend on the input size but rather on half the input size. When the input size
decreases on each iteration or step, an algorithm is said to have logarithmic
time complexity.
Consider following example:
const binarySearch = (array, target) => {
let firstIndex = 0;
let lastIndex = array.length - 1;
while (firstIndex <= lastIndex) {
let middleIndex = Math.floor((firstIndex + lastIndex) / 2);
if (array[middleIndex] === target) {
return middleIndex;
}
if (array[middleIndex] > target) {
lastIndex = middleIndex - 1;
} else {
firstIndex = middleIndex + 1;
}
}
return -1;
};
let score = [12, 22, 45, 67, 96];
console.log(binarySearch(score, 96));
This is an implemntation of binary search algorithm to find the index
of a given element in an array:
In the code above, you first get the middle index of your array, compare
it to the target value, and return the middle index if it is equal.
Otherwise, you must check if the target value is greater or less than the
middle value to adjust the first and last index, reducing the input size
by half.
Because for every iteration the input size reduces by half, the time
complexity is logarithmic with the order O(log n).
Quadratic Time: O(n^2):
When you perform nested iteration, meaning having a loop nested inside a
another loop, the time complexity is quadratic.
Consider a code below:
const matchElements = (array) => {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
if (i !== j && array[i] === array[j]) {
return `Match found at ${i} and ${j}`;
}
}
}
return "No matches found 😞";
};
const fruit = [1,2,3,4,5,2,3,4];
console.log(matchElements(fruit)); // "Match found at 1 and 5"
W.r.t. above code ,if you have an array with n items. In wrost case
scenario the outer loop will run n times, and the inner loop will run n
times for each iteration of the outer loop, which will give total n^2
operations. If the array has ten items, ten will need 100 operations
i.e. (10^2).
In the example above, there is a nested loop, meaning that the time
complexity
is quadratic with the order O(n^2).
Exponential Time: O(2^n):
You get exponential time complexity when the growth rate doubles with each
addition to the input (n), often iterating through all subsets of the input
elements. Any time an input unit increases by 1, the number of operations
executed is doubled.
Consider following example:
const recursiveFibonacci = (n) => {
if (n < 2) {
return n;
}
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};
console.log(recursiveFibonacci(6)); // 8
Here when n is 0,1,2 then only it requires one operation but once n goes
on increasing for each n greater than 2 it requres 2 recursive calls to
function recursiveFibonacci() where it execute following statement.
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
Hence the function "recursiveFibonacci" makes two recursive calls for
each input value n,resulting in an exponential time complexity of O(2^n).
Log linear time: O(n log n):
Consider following code example it is an implementation of quick sort
algorithm in javaascript.
function quickSort(array) {
if (array.length == 0 || array.length == 1) {
return array;
} else {
let pivot = array[0];
let left = [];
let right = [];
//this loop takes n operation for array length n
for (let i = 1; i < array.length; i++) {
if (array[i] <= pivot) {
left.push(array[i]);
}
if (array[i] > pivot) {
right.push(array[i]);
}
}
//2 recursive call for each input
return [...quickSort(left), pivot, ...quickSort(right)];
}
}
let result = quickSort([
1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92,
]);
console.log(result);
The quickSort function has a time complexity of O(n log n) on average. This is
because in each recursive call, the function partitions the array into two
subarrays based on a pivot element, which takes O(n) time. The function then
recursively calls itself on the left and right subarrays, resulting in a total
time complexity of O(n log n) on average.
If you want examples of Algorithms/Group of Statements with Time complexity
as given in the question,here is a small list
O(1) time:
a) Accessing Array Index (int a = ARR[5];)
b) Inserting a node in Linked List
c) Pushing and Poping on Stack
d) Insertion and Removal from Queue
e) Finding out the parent or left/right child of a node in a tree stored
in Array
f) Jumping to Next/Previous element in Doubly Linked List Accessing Array
Index (int a = ARR[5];)
g) Inserting a node in Linked List
h) Pushing and Poping on Stack
i) Insertion and Removal from Queue
j) Finding out the parent or left/right child of a node in a tree stored
in Array
k) Jumping to Next/Previous element in Doubly Linked List
O(n) time:
In a nutshell, all Brute Force Algorithms, or Noob ones which require
linearity, are based on O(n) time complexity
a) Traversing an array
b) Traversing a linked list
c) Linear Search
d) Deletion of a specific element in a Linked List (Not sorted)
e) Comparing two strings
f) Checking for Palindrome
g) Counting/Bucket Sort and here too you can find a million more such
examples....
O(log n) time
a) Binary Search
b) Finding largest/smallest number in a binary search tree
c) Certain Divide and Conquer Algorithms based on Linear functionality
d) Calculating Fibonacci Numbers - Best Method The basic premise here is
NOT using the complete data, and reducing the problem size with every
iteration
O(n log n) time
The factor of 'log n' is introduced by bringing into consideration Divide
and Conquer. Some of these algorithms are the best optimized ones and used
frequently.
a) Merge Sort
b) Heap Sort
c) Quick Sort
d) Certain Divide and Conquer Algorithms based on optimizing O(n^2)
algorithms
O(n^2) time
These ones are supposed to be the less efficient algorithms if their
O(nlogn) counterparts are present. The general application may be Brute
Force here.
a) Bubble Sort
b) Insertion Sort
c) Selection Sort
d) Traversing a simple 2D array
O(n!) time
a) Solving the travelling salesman problem via brute-force search
b) generating all unrestricted permutations of a partially ordered set;
c) finding the determinant with Laplace expansion
d) enumerating all partitions of a set
No comments:
Post a Comment