Revisiting Data Structures and Algorithms - Big O Notation

I am learning about data structures and algorithms again.

A while ago I wanted to try Leetcode to get better at solving code problems. It was good practice, but I found that if I picked random problems to work on, I could usually come with a solution, but the problems sometimes are testing your knowledge of specific algorithms. How am I supposed to get the “correct” answer if I have never studied the algorithm? I don’t want to just google the answer to every question, this defeats the whole purpose.

I figured I should try learning more algorithms, and once I learn them, then I should practice them.

This time around for data structures and algorithms, I found a course that teaches this topic for JavaScript. The first lesson is on Big O Notation.

This course is the JavaScript Algorithms and Data Structures Masterclass on Udemy.

I generally understand the concepts behind Big O, but I sometimes struggle to analyze the time and space complexity for different solutions to a problem.

Counting operations

The idea here is that to analyze a solution, you need to have a general idea of how much time (or space) it is taking. Going through the code, you count all of the operations and assignments that are taking place.

You don’t need the most accurate tally. It’s about noticing general trends. Let’s say your function takes an argument n, a number. If you notice that your code often does something n times, it will take longer to complete as the value of n grows.

Big O Notation

Describes the relationship of the input size of a function, and time it takes to run. It’s about describing overall trends. We are talking about the worst case scenario, or the upper bounds. For example, if you have an input of a large array, and the function is searching that array for a specific item, we have to assume that we need to search the whole array, even if in reality, the item is found earlier.

Time complexity is the time it takes an algorithm to run.

Some examples:

O(1) is constant - it means that no matter what n is, the time will be about the same.

O(n) is linear - as n grows, the time takes longer

O(n^2) is quadratic - as n grows, the time increases exponentially

Simplifying

Let’s say there are 10 operations that happen in this function, 10n. We don’t need to worry about the 10, and just simplify to n. We just care about what happens as the input grows.

In general, constants don’t matter, and we can get rid of them. It’s about comparing the different algorithms to each other.

Example: O(n^2 + 5n + 8) simplifies to n^2. This is because if you plug in a large number for n, 5n and 8 are tiny in comparison to n^2, so we can ignore them.

Rule of thumb:

• arthimetic operations are constant
• variable assignment is constant
• accessing items in an array by index, or object by key, is constant
• loops: the complexity is the length of the loop times the complexity of whatever is inside the loop - that’s why we multiply n for nested loops

Just need to worry about what happens as n grows - not what happens when n is small.

Space complexity

Space complexity - the space, or memory, required by an algorithm.

Rules of thumb:

• most primitive, except for strings, are constant space - booleans, numbers, undefined, and null
• strings are O(n), n being the length of the string
• reference types are also O(n) - for arrays, n is the length, and for objects,n is the number of keys

Logarithms

Reminder of how logs work: logs are the inverse of exponentiation.

They work like this: log2(value) = exponent => 2^exponent = value

Rule of thumb: The logarithm of a number roughly measures the number of times you can divide that number by its base before you get a value that’s less than or equal to one.

Example:

log2(8) = 3

// divide 8 by 2 as many times as you can before geting to 1 (or less)

8 / 2 = 4
4 / 2 = 2
2 / 2 = 1

// it took 3 operations, so the answer is 3.

//Also, 2 to the power of 3 = 8 (2 * 2 * 2)

Here’s a khanacedemy article explaining logarithms in a beginner friendly way.

O(log(n)) is one of the best ones you can have, second to constant time. On a graph, it is essentially the opposite of an exponential graph - after an initial increase, the curve flattens out.