This content originally appeared on DEV Community and was authored by Tim Mailu
All developers to strive to write ‘optimal code’. A well-seasoned developer will most likely be acquainted with the phrase ‘optimal code’ but for the newbies, let’s dive in. Optimal code refers to code that is faster, takes up less memory and is readable. This is achieved through Data Structures - the different ways we can choose to arrange or store data in our computers. Let's look at fast code
Time Complexity and The Big 'O' Notation
Time complexity is how can we analyze the runtime of an algorithm as the size of the inputs increases and The Big O Notation is just a way for us to talk formally about how the runtime of an algorithm grows as the inputs grows
We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases
let's look at the code below:
function addUpTo(n) {
return n * (n + 1) / 2;
}
No matter the size of "n", there will always be 3 operations in the code above i.e multiplication, addition and division. We say the above code has a Big O Notation of O(1). Let's look at another example
function addUpTo(n) {
let total = 0;
for (let i = 1; i <= n; i++) {
total += i;
}
return total;
}
In the above example, the subsequent number of operations the loops goes through is anchored to the value of the argument 'n'. The number of operations is bounded by a multiple of n- Big O notation of O(n). We're more interested in the trend in relationship which can take many forms for instance:
- f(n) could be linear (f(n) = n)
- f(n) could be quadratic (f(n) = n )
- f(n) could be constant (f(n) = 1)
- f(n) could be something entirely different!
Space Complexity
We can also use big O notation to analyze space complexity: how much additional memory do we need to allocate in order to run the code in our algorithm i.e space required by an algorithm, not including space taken up by the inputs.
Some important points to note:
- Most primitives (booleans, numbers, undefined, null) are constant space
- Strings require O(n) space (where n is the string length)
- Reference types are generally O( n), where n is the length (for arrays) or the number of keys (for objects)
function double(arr) {
let newArr = [];
for (let i = 0; i < arr.length; i++) {
newArr.push(2 * arr[i]);
}
return newArr;
}
We can observe that the above code has a Big O notation of O(1) – constant complexity – i.e,requires the same amount of space regardless of the input size
Hopefully, in reading this blog, you’ve gained some insight about time and space complexity
This content originally appeared on DEV Community and was authored by Tim Mailu
Tim Mailu | Sciencx (2022-06-19T20:14:11+00:00) Data Structures and Algorithms-Intro. Retrieved from https://www.scien.cx/2022/06/19/data-structures-and-algorithms-intro/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.