Suppose you are working in a big company, or in your own company, and your project or your "code snippet" is going to be used for millions of people. You want that your code run fast, consume the lower amount of memory resources.
Imagine you are developing a search engine like Google, Amazon, Facebook (name it) to compete with leaders or to stand out above others you need 2 main things:
- Your code needs to run fast.
- Your code needs to use the lower memory you can.
Measure velocity
How can you measure the time your code needs to solve a problem?
Yes, remember, your code exists to solve a problem:
- Retrieve data from a database
- Search in a graph or in a binary tree (like indexes do in a NoSQL database)
- Get the grater value in an array of objects, and so on...
In Computer Science the sequence of instructions that we use to solver a class of problems or to perform a computation is known as an algorithm.
So, an algorithm is just that, a chunk of code that you write in any language that solves a problem.
The more your solution (algorithm) uses PC memory or has a lot of loops the more time it takes to solve the problem and that is not a good sign of good code. But how you can measure that time? Well that time is just elementary operations, imagine your code (algorithm) is reading (accessing) a memory slot in your PC.
Time, like seconds, minutes are not a good reference point to get to know how fast is your code, that's because it depends on your computer RAM, how many operations are being executed...
You need to add more reference points, like how many operations (instructions) your algorithm executes and also the amount of inputs. You need to analyze all these factors to get to know the complexity of your code (algorithm).
So far...
We have been talking about:
- Just the time is not a good reference point to know how good is your solution (algorithm)
- You need to consider the amount of inputs.
- and how many instructions your solution execute
Complexity analysis
Complexity analysis is the way to know what makes a problem solution better than other solution.
Complexity analysis is the result of add tow things:
"how fast your algorithm run" and "how much memory it uses " your result is "complexity analysis"; you are adding time and space.
So far...
The time and space complexity actually measure the speed or the extra memory an algorithm takes up.
How this 2 "variables" change as the input size of an algorithm increases.
It's my code fast?
You should ask that question to Big O. Why? because Big O notation is the language we use (in interviews)for talking about how long an algorithm takes to run.
See that I highlight in interviews because the O notation's family is bigger. We have Omega, Theta, etc.
Big O, response how time scales with respect to some input variables. We express the runtime in terms of how quickly it grows relative to the input, as the input gets arbitrary large.
In Big O notation: the bigger the size of the input (aka: "n") the more time your algorithm needs to run.
So far...
- We call the size of the input "n"
- Time complexity: Measure the speed of an algorithm respect of the size of the input. This is called asymptotic analysis. This study the behavior of the function(n) as the values n tends towards infinity.
Notation
let fruits = ["🍏", "🍌", "🍒"];
// get the first element in the array
const first = fruits[0]; // 🍏
Notation: O(1) or constant time. You can figure it out yourself that, no matter how many elements your array has, you only need 1 operation to get the first element in the array.
let fruits = ["🍏", "🍌", "🍒"];
// iterate over the array
for (let fruit of fruits) {
console.log(fruit); //"🍏", "🍌", "🍒"
}
Notation: O(n) or linear time. You can figure it out yourself that, you need to traverse all the array to print out all elements in the array. The biggest the size of the input, the more time you code needs to solve the problem.
const mammals = ["🦁", "🐴", "🐘"];
// make a pair of each mammals
for (let i=0; i < mammals.length; i++) {
for (let j=i; j < mammals.length; j++) {
console.log(mammals[i], mammals[j]);
//"🦁" "🦁", "🦁" "🐴", "🦁" "🐘", "🐴" "🐴", "🐴" "🐘", "🐘" "🐘"
}
}
Notation: O(n²) or quadratic time. As you can see in this algorithm takes an exponential time to be solved if the size of the input grows.
You can use the following table to response the previous question, it's my code fast?
Rules
So far we know how to apply Big O notation to our code, but we need to apply some rules to get a more accurate notation.
1. Different steps get added
let fruits = ["🍏", "🍌", "🍒"];
const twoBagsOfFruits = (fruits) => {
// first bag (iteration)
for (let fruit of fruits) {
console.log(fruit);
}
// second bag (iteration)
for (let fruit of fruits) {
console.log(fruit);
}
}
Since the first and the second loop notation is O(n), we can say that the result is: O(2n)
2. Drop Constants
In the previous rule the result was O(2n) and we can refactor that result with this new rule. So, if we have to drop constants, our new result will be: O(n); realize that we just get rid of the constant 2.
3. Drop less significant terms
const mammals = ["🦁", "🐴", "🐘"];
const zoo = (mammals) => {
// make a pair of each mammals
for (let i=0; i < mammals.length; i++) {
for (let j=i; j < mammals.length; j++) {
console.log(mammals[i], mammals[j]);
}
}
// just mammals please
for (let animal of mammals) {
console.log(animal);
}
}
The first nested loops the notation is O(n²), the second one is O(n), so the result is: O(n² + n); but if we apply this definition (drop less significant terms) we get: O(n²).In this case n is less significant than n².
4. Different inputs => Different variables
With this rule you need to take into account all the different variables that that plays in your algorithm:
let fruits = ["🍏", "🍌", "🍒"];
const mammals = ["🦁", "🐴", "🐘"];
const twoBagsOfFruits = (fruits, mammals) => {
for (let i = 0; i < mammals.length; i++) {
for (let j = 0; j < fruits.length; j++) {
console.log(mammals[i], fruits[j]);
}
}
}
As you can see here we are passing two different arrays (arguments) to the function expression. Remember that we decide to call the size of the input n? Now, since there are two different inputs we are going to call them:
for the first input (fruits): n
for the second input (mammals): m
Good to know
We always talk about the worst-case scenario. Check out this example...
function seek (haystack, needle) {
for (let i = 0; i < haystack.length; i++) {
if (haystack[i] === needle) return true;
}
return false
}
As you can figure it out we can find the needle in the first iteration and we get O(1), but in the worst case we get O(n) and we find the needle in the last iteration. In general we'd say that is O(n), we always talk about the worst-case scenario.
Space complexity
Remember that complexity analysis it's made by two factors: time and space. We just analyze the time, now we are going to analyze the space. Don't worry, this one less complicate that the previous one...
Sometimes we want to optimize for using less memory instead of using less time. (We simply look at the total size o any new variable we're allocating)
function log(n) {
for (let i = 0; i < n.length; i++) {
console.log(i);
}
}
You already know that:
time is → O(n)
Now we are going to check space analysis
space is → O(1)
and that's because i is the only variable we are allocating in memory, we are using just 1 more variable to solve a problem. Let's see another example:
function x (n) {
let arr = [];
for (let i = 0; i < n.length; i++) {
arr[i] = n[i]
}
return arr;
}
time is → O(n)
space is → O(n)
Here we are using just 1 variable (arr), but we are allocating n values in the array. So, if the number of inputs grows so does arr (the size of memory allocations).
Conclusion
I hope you already know how to analyze time-space complexity in interviews, since this one of the basics of interview questions. You should analyze it every time you solve an algorithm and also know when to prioritize space over time and vice versa.
Top comments (0)