Big O Notation - rohit120582sharma/Documentation GitHub Wiki

Introduction

To analyze the performance of an algorithm, we use Big O Notation.

Big O can give us a high level understanding of time or space complexity of an algorithm.

We can use Big O notation to analyze time complexity: how long an algorithm takes to run depending on how long is the input? It basically measures the number of operations.

We can 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?

Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

The time or space complexity (as measured by Big O) depends only on the algorithm, not the hardware used to run the algorithm.


Types

O(1) - Constant Time Complexity

It describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.

O(N) - Linear

It describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.

O(N^2) - Quadratic

It represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set.

O(2^N) - Exponential

It denotes an algorithm whose growth doubles with each additon to the input data set. An example of an O(2^N) function is the recursive calculation of Fibonacci numbers.


Time Complexity

An algorithm is a self-contained step-by-step set of instructions to solve a problem. It takes time for these steps to run to completion. The time it takes for your algorithm to solve a problem is known as time complexity.

Rules of thumb

  • 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

Space Complexity

Rules of thumb

  • 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)

Logarithms

A logarithm is the inverse of exponentiation.

Rules of thumb

  • 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.
⚠️ **GitHub.com Fallback** ⚠️