Big (O) notation ?? What is Time Complexity and Space Complexity ?
Objectives:
Describe what Big O notation is
Simplify Big O expressions
Define “time complexity” and “space complexity”
Evaluate the time complexity and space complexity of different algorithms using Big O notation
Describe what a logarithm is
What’s the idea here:
Imagine we have multiple implementations of the same function or same problem or same algorithm.
How can we determine which one is the “best?”
For example: “Write a function that accepts a string input and returns a reversed copy”. This problem had more than 10 ways of implementations but, how do we know which one is the “best”. Simply, Big O notation means numerical notation of a program.
Why Do We Care?
When you are working in a software company or in a technical interview like“FAAMN” (Facebook, Apple, Amazon, Microsoft,Netflix) tech giant companies.
It’s important to have a precise vocabulary to talk about how our code performs.
Useful for discussing trade-offs between different approaches.
When your code slows down or crashes,identifying parts of the code that are inefficient can help us find pain points in our application.
An Example: “Suppose we want to write a function that calculates the sum of all numbers from 1 up to (and including) some number n”
/////////// < < Naive Approach for above program >> //////////////////
/* functionname: addUpTo
Input: Number
Output:Number
Desc: Add values from 1 to given range
Time Complexity: O(n)
Space Complexity: O(1)
*/
Code
function addUpTo(n) {
let total = 0;
for (let i=0;i ≤n;i++) {
total +=i;
}
return total; // loop iteration is over we are returning the total
}
addUpTo(8);
/////////// < < Linear Approach for above program >> ////////////////
using Math
function addUpTo(n) {
return n*(n-1)/2;
}
addUpTo(8);
Which one is better ?
What does better mean?
Faster?
Less memory-intensive?
More readable?
Note: Faster means we should not calculate the performance of a program by using run time of a program , like how much time it will take to execute a function.
The Problem with Time
Different machines will record different times.
The same machine will record different times!
For fast algorithms, speed measurements may not be precise enough?
If not time, then what?
Rather that counting seconds, which are so variable..
count the number of simple operations the computer has to perform.
Let’s Go back to second math code approach in that there is only three operations regardless of the size of n. i.e., multiplication, addition and division.
Now, check the first naive approach
The number of operations can be as low as 2n or as high as 5n + 2.
But regardless of the exact number, the number of operations grows roughly proportionally with n.
If n doubles, the number of operations will also roughly double.
Introducing ….Big O
- Big O Notation is a way to formalize fuzzy counting
- It allows us to talk formally about how the runtime of an algorithm grows as the inputs grow.
Big O Definition
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
- 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!
Example 1
// Always 3 operations Time Complexity is O(n)
// The operations are * , + , /
function addUpTo(n) {
return n * (n + 1) / 2;
}addUpTo(6);
Example 2
// In this naive approach the time complexity is based on “Number of operations is (eventually) bounded by a multiple of n” . Time Complexity is O(n).
function addUpTo(n) {
let total = 0;
for (let i = 1; i <= n; i++) {
total += i;
}
return total;
}addUpTo(6);
Another Example:
Count values from up and down
function countUpAndDown(n) {
console.log(“Going up!”);// This loop is O(n)
for (let i = 0; i < n; i++) {
console.log(i);
}
console.log(“At the top!\nGoing down…”);
// This loop is O(n)for (let j = n — 1; j >= 0; j — ) {
console.log(j);
}
console.log(“Back down. Bye!”);
}
Number of operations is (eventually) bounded by a multiple of n . Time Complexity is O(n).
One More Example
print all pairs from the given number.
function printAllPairs(n) {
// Outer for loop is O(n)
for (var i = 0; i < n; i++) {// Inner for loop is O(n)
for (var j = 0; j < n; j++) {
console.log(i, j);
}
}
}
O(n) operation inside of an O(n) operation. Time Complexity is O(n²).
For better understanding the input and time correlate follow this Performance Tracker tool
https://rithmschool.github.io/function-timer-demo/
Simplifying Big O Expressions
When determining the time complexity of an algorithm, there are some helpful rule of thumbs for big O expressions.
These rules of thumb are consequences of the definition of big O notation.
Constants Don’t Matter
O(2n) ==> O(n)
O(500) ==> O(1)
O(13n²) ==> O(n²)
Smaller Terms Don’t Matter
O(n + 10) ==> O(n)
O(1000n + 50) ==> O(n)
O(n²+5n+8) ==> O(n²)
Big O Short-hands
- Arithmetic operations are constant
- Variable assignment is constant
- Accessing elements in an array (by index) or object (by key) is constant.
- In a loop, the the complexity is the length of the loop times the complexity of whatever happens inside of the loop
For In-detail Understanding
Space Complexity
So far, we’ve been focusing on time complexity: how can we analyze the runtime of an algorithm as the size of the inputs increases?
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?
What about the inputs?
Sometimes you’ll hear the term auxiliary space complexity to refer to space required by the algorithm, not including space taken up by the inputs.
Unless otherwise noted, when we talk about space complexity, technically we’ll be talking about auxiliary space complexity.
Space Complexity in JS
- 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)
Example
In this function, we are doing two assignments i.e., let total =0 and let i=0, Space Complexity is O(1). Time Complexity O(n).
function sum(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) {
total += arr[i];
}
return total;
}
Another Example
In this function, we are double the array elements and push those values to new array. so, we are returning the n numbers. Space Complexity is O(n).
function double(arr) {
let newArr = [];
for (let i = 0; i < arr.length; i++) {
newArr.push(2 * arr[i]);
}
return newArr;
}
We are done with Space Complexity and Time Complexity . let’s take a look at logarithms.
Logarithms
- We’ve encountered some of the most common complexities: O(1), O(n), O(n²).
- Sometimes big O expressions involve more complex mathematical expressions.
- One that appears more often than you might like is the logarithm!
Wait, What’s a log again?
- log2(8) = 3 ===> 2³ =8
- log2(value) = 8 ===> 2^exponent =value
- log ==== log2
- The logarithm of a number roughly measures the number of times you can divide that number by 2 before you get a value that’s less than or equal to one.
Logarithm Complexity
Logarithmic time complexity is great!
Why do we care?
- Certain searching algorithms have logarithmic time complexity.
- Efficient sorting algorithms involve logarithms.
- Recursion sometimes involves logarithmic space complexity and much more.
RECAP
- To analyze the performance of an algorithm, we use Big O Notation
- Big O Notation can give us a high level understanding of the time or space complexity of an algorithm
- Big O Notation doesn’t care about precision, only about general trends (linear? quadratic? constant?)
- The time or space complexity (as measured by Big O) depends only on the algorithm, not the hardware used to run the algorithm
- Big O Notation is everywhere, so get lots of practice!
Thank you, for taking your valuable time to read this, if any suggestions feel free to comment below . I am happy to improve myself.
