# 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
}

}``````

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