Data Structures and Algorithms-Intro

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, lets 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, youve gained some insight about time and space complexity