Algorithms & Data Structures - Day 1April 03, 2020

Everyone tells me I don’t need a CS degree to be great at building things.

While I believe them, I still have a sense of void in my basic understanding of how computers work. I had my first computers 3 years ago (2017). Before then, I couldn’t shut down one to save my own life.

What exactly do I want to learn?

I honestly don’t know what to expect… My compass are the things that excite me. Lately, I’ve been interested in computer science concepts like

  • Data structures
  • Algorithms
  • Systems Design

I don’t want to be a CS prof, but I strongly believe understanding these basics will make me a better engineer

What language?

JavaScript

I was thinking of C or C++, but I write JS everyday and I could easily apply the concepts I learn.

I feel JavaScript abstracts a lot of CS stuff. I’ve been writing JS professionally for about a year now but recently picked up C# (Like 2 months ago). I’ve learned a lot from writing code in an Object oriented, classical, strongly typed language. Infact, my exposure to C# has sprung this desire to learn the basics.

But JS it is…

Day 1

Big O Notation

  • What is Big O Notation?
  • Time and Space complexity

Big notation is a framework for comparing performance of code solutions

Let’s imagine we want to write a function that adds all the numbers from 1 up to n. We could make use of one of the following

const addUpTo = n => {
  let total = 0
  for (let i = 1; i <= n; i++) {
    total += i
  }

  return total
}

Or we could make use of

const addUpTo = n => {
  return (n * (n + 1)) / 2
}

While they both work, the first takes about 1.24s to add from 1 to 1,000,000,000 (a billion). The second takse 0.000100…

Men. That’s a lot!

The reason the first takes a lot of time is because of the number of operations that have to be done. total += 1 happens on every iteration of the loop. for(let i = 0; i <= n; i++) contains another operation that happens on every loop. The number of operations the computer has to perform grows as n grows.

Compare this with the second solution that has only 3 operations irrespective of how large n is. This implementation has O(1) (Big O of 1). This means as n grows, it has no effect on the runtime.

The previous solution has a Big O of O(n). This means that as n grows, the number of operations grow.

Take for another example

const printAllPairs = n => {
  for (var i = 0; i < 0; i++) {
    for (var j = 0; j < n; j++) {
      console.log(i, j)
    }
  }
}

This function has 2 loops. O(n) + O(n) = O(n2). This means, as n grows, the number of operations grow at n2

Big O Shorthands

  • Arithmetic operations are constant. +, -, / all have the same magnitude irrespective of the operand
  • Variable assignment is constant
  • Accessing elements in an array (by index) or object (by key) is constant
  • In a loop, the complexity is the length of the loop times the complexity of whatever happens inside the loop

Time & Space Complexity

  • Time complexity refers to how much time the system needs to execute the code block
  • Space complexity refers to how much memory the system needs to execute the code block

That’s all for day 1. See you tomorrow