What is "Big O"?
Big O notation is a mathematical notation used to describe the performance of an algorithm. It measures the time and space complexity of an algorithm, which is the amount of time and memory it takes to run a specific task.
That's maths. Why do I need to know about it?
As web developers, it's important to understand Big O notation because it helps us evaluate the efficiency of our code. This allows us to identify potential bottlenecks and optimise our algorithms for better performance.For example, if we have a sorting algorithm that takes an input of n items, we can use Big O notation to determine the time and space complexity of the algorithm. If the algorithm has a time complexity of O(n2), it means that it will take n2 operations to sort the input. On the other hand, if the algorithm has a time complexity of O(n log n), it will take n log n operations to sort the input.
In addition to helping us optimise our code, understanding Big O notation also allows us to make informed decisions when choosing algorithms for specific tasks. For example, if we need to sort a large dataset, we may choose an algorithm with a time complexity of O(n log n) over an algorithm with a time complexity of O(n2) because it will be more efficient and require less time and memory to run.
In short, knowing about Big O notation is essential for web developers because it helps us understand the performance of our algorithms and make informed decisions about which algorithms to use for specific tasks.
Here is a list of the common Big O complexities, along with their names and formulas:
- O(1) - Constant time complexity. The running time of the algorithm does not depend on the input size.
- O(log n) - Logarithmic time complexity. The running time of the algorithm increases as the logarithm of the input size.
- O(n) - Linear time complexity. The running time of the algorithm is directly proportional to the input size.
- O(n log n) - Log-linear time complexity. The running time of the algorithm is the product of the input size and the logarithm of the input size.
- O(n2) - Quadratic time complexity. The running time of the algorithm is the square of the input size.
- O(n3) - Cubic time complexity. The running time of the algorithm is the cube of the input size.
- O(2n) - Exponential time complexity. The running time of the algorithm is the power of 2 to the input size.
- O(n!) - Factorial time complexity. The running time of the algorithm is the factorial of the input size. (You do NOT want this)
A quadratic function, also known as O(n2), is a mathematical function in which the time complexity is proportional to the square of the input size. This means that as the input size increases, the number of operations required to run the algorithm increases exponentially.
Here is an example of a JavaScript code that is O(n2):
function findDuplicates(arr) {
let duplicates = [];
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (arr[i] === arr[j] && i !== j) {
duplicates.push(arr[i]);
}
}
}
return duplicates;
}
In this code, we are using nested for loops to find duplicate elements in an array. The time complexity of this algorithm is O(n2) because the number of operations required to run the algorithm is proportional to the square of the input size.
As the input set of the algorithm increases, the efficiency of the code is greatly affected. For example, if we have an input set of 10 items, the algorithm will take 100 operations to run. However, if we have an input set of 100 items, the algorithm will take 10,000 operations to run. This means that the larger the input set, the slower the algorithm will run and the more memory it will require.
Therefore, it's important to avoid using O(n2) algorithms when dealing with large input sets because they can be very inefficient and slow. Instead, we should choose algorithms with a lower time complexity, such as O(n log n), to improve the performance of our code.
Comparing complexity of different search algorithms
A linear search is a simple search algorithm that involves examining each element of a list, one at a time, in sequential order, until the desired element is found or the end of the list is reached. In contrast, a binary search algorithm is a more efficient search algorithm that uses a divide-and-conquer strategy to quickly find an element within a sorted list.
Here is an example of a linear search algorithm in JavaScript:
function linearSearch(list, target) {
for (let i = 0; i < list.length; i++) {
if (list[i] === target) {
return i;
}
}
return -1;
}
And here is an example of a binary search algorithm in JavaScript:
function binarySearch(list, target) {
let left = 0;
let right = list.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (list[mid] === target) {
return mid;
} else if (list[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
One key difference between these two algorithms is their time complexity, or the amount of time it takes for the algorithm to run. A linear search has a time complexity of O(n), where n is the number of elements in the list, because it must examine each element in the worst case. In contrast, a binary search has a time complexity of O(log n), because it repeatedly divides the search space in half until the desired element is found. This means that for large lists, a binary search can be significantly faster than a linear search.
Another difference between these algorithms is the types of lists they can be used with. A linear search can be used with any type of list, regardless of whether the elements are sorted or not. In contrast, a binary search can only be used with a sorted list, because the algorithm relies on the list being in a specific order to divide the search space in half at each step.
Overall, a binary search is a more efficient search algorithm than a linear search, but it can only be used with sorted lists.
Fibonacci
The Fibonacci sequence is a sequence of numbers in which each number is the sum of the two preceding numbers, starting with 0 and 1. In mathematical terms, the sequence can be defined as follows:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1
For example, the first few numbers in the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The sequence is named after the Italian mathematician Leonardo Fibonacci.
Here is an example of a recursive function in JavaScript that calculates and prints the first 5 Fibonacci numbers:
// fibonacci algorithm using recursion
function recursiveFibonacci(num) {
if (num <= 1) return 1;
return recursiveFibonacci(num - 1) + recursiveFibonacci(num - 2);
}
// print the first 5 fibonacci numbers
for (let i = 0; i < 5; i++) {
console.log(recursiveFibonacci(i));
}
This function uses a recursive approach to calculate each Fibonacci number. It uses the fact that the n-th Fibonacci number can be calculated as the sum of the (n-1)-th and (n-2)-th Fibonacci numbers. The function uses a base case of n <= 1, which returns the value of n directly, to prevent the recursion from continuing indefinitely.
Here is an example of a non-recursive function in JavaScript that calculates and prints the first 5 Fibonacci numbers:
function fibonacci(n) {
let a = 0;
let b = 1;
let c;
if (n === 0) {
return a;
}
for (let i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
for (let i = 0; i < 5; i++) {
console.log(fibonacci(i));
}
This function uses a loop to iteratively calculate each Fibonacci number. It uses the fact that the n-th Fibonacci number can be calculated as the sum of the (n-1)-th and (n-2)-th Fibonacci numbers. The function uses a special case for n = 0, which returns 0 directly, because the 0-th Fibonacci number is defined to be 0.
In the case of the Fibonacci sequence, the size of the input is the index of the Fibonacci number to be calculated, which we will call n. The recursive algorithm has a time complexity of O(2n), because each call to the fibonacci() function makes two recursive calls. This means that the algorithm will take an exponentially longer time to complete as the input size increases.
In contrast, the non-recursive algorithm has a time complexity of O(n), because it uses a loop to iteratively calculate each Fibonacci number. This means that the algorithm will take a linear amount of time to complete, regardless of the input size.
Therefore, the non-recursive algorithm is the more efficient solution to the problem of calculating Fibonacci numbers, because it has a lower time complexity. This means that it will take less time to run for large input sizes, and it will be able to handle larger inputs without running out of memory or taking an excessively long time to complete.
Final Thoughts
As a developer we want our code to run as quickly and efficiently as possible. Knowing an algorithm's complexity can help you decide whether you need to investigate other options.
Comments
Post a Comment