Big O Notation

#javascript #html #css #webdev

                   -Intro to Big O
                   -Timing Our Code
                   -Counting Operations
                   -Official Intro to Big O 
                   -Simplifying Big O Expressions
                   -Space Complexity
                   -Logs

Intro to Big O

Big O allows us to determine how fast and efficient some code will run.

There are many different ways to program a solution to a problem. However, some ways are faster than others for solving a problem. Big O makes it possible to compare code against other pieces of code to get the best performance.

Big O Notation can be broken into 3 different categories.
O(1) is always 3 operations


 function addUpTo(n) {
 return n * (n + 1) / 2; 
 }

O(n) is number of operations is bounded by a multiple of n (10n)


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

O(n^2) is an operation inside of an another operation.


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

Timing Our Code

Good code is optimized for speed and efficiency. It is possible to have bloated code that is unnecessary. Unnecessary code can mean an application may appear to be slow. When your code slows down or crashes, identifying parts of the code that are inefficient can help us find pain points in our approach.

Counting Operations

Rather than counting seconds, count the number of simple operations that computer has to perform.

Depending on what we count, 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 grow roughly proportionally with n.

Official Intro to Big O

Big O Notation is a way to formalize fuzzy counting. It allows us to talk formally about the runtime of an algorithm
grow as the inputs grow.

Describe the relationship between the input to a function or as it grows and how it changes the runtime of that function.

The relationship between the input size and the time relative to that input size and the time relative to that input.

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 contant time f(n) as n increases.

f(n) could be linear (f(n) = n)
f(n) could be quadratic (f(n) = n^2)
f(n) could be constant (f(n) = 1)
f(n) could be something different

Simplifying Big O Expressions

Analyzing complexity with Big O can get complicated. The rules won't always work but are a helpful starting point.

Arithmetic Operations are constants
Variable assignment is constant
Accessing elements in 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 of the loop.

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 input increases?

Now lets focus on what happens to the space that an algorithm that takes up as the size of the input 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?

Auxiliary space complexity refers to the space required by the algorithm, not including space taken up by the inputs.

Rules for space complexity

Most primitives (booleans, numbers, undefined, null) are constant space.
Strings require O(n) space (where n is the string length)
Reference types are O(n), where n is the length (for arrays) or the number of keys (for objects)

Logs

Certain searching algorithms have logarithmic time complexity. Efficient sorting algorithm involves logarithm. Recursion sometimes involves logarithmic space complexity.