About Big O

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.  // by Wikipedia

Big Os

• O(1) –> Constant- no loops
• O(n) –>Linear- for loops, while loops through n items
• O(log N) –> Logarithmic- usually searching algorithms have log n if they are sorted (Binary Search)
• O(n log(n)) –> Log Linear- usually sorting operations
• O(n^2) –> Quadratic- every element in a collection needs to be compared to ever other element. Two nested loops
• O(2^n) –> Exponential- recursive algorithms that solves a problem of size N
• O(n!) –> Factorial- you are adding a loop for every element

*Iterating through half a collection is still O(n)

*Two separate collections: O(a * b)

What can cause time in a function?

• Operations (+, -, *, /)
• Comparisons (<, >, ==)
• Looping (for, while)
• Outside Function call (function())

Rule Book

• Rule 1: Always worst Case
  –> even there is a “break” condition inside the for loop, think the worst case that the beak point is the last item in the loop
• Rule 2: Remove Constants
• Rule 3: Different inputs should have different variables. O(a+b). A and B arrays nested would be O(a*b)
  + for steps in order
  * for nested steps
• Rule 4: Drop Non-dominant terms

What causes Space complexity

• Variables
• Data Structures
• Function Call
• Allocations

Examples

example1

// What is the Big O of the below function? (Hint, you may want to go line by line)
function funChallenge(input) { 
  let a = 10; //O(1)
  a = 50 + 3; //O(1)

  for (let i = 0; i < input.length; i++) { //O(n)
    anotherFunction(); //O(n)
    let stranger = true; //O(n)
    a++; //O(n)
  }
  return a; //O(1)
}

A: O (n) –> big O (3+4n)

example2

// What is the Big O of the below function? (Hint, you may want to go line by line)
function anotherFunChallenge(input) {
  let a = 5; //O(1)
  let b = 10;//O(1)
  let c = 50;//O(1)
  for (let i = 0; i < input; i++) {
    let x = i + 1;//O(n)
    let y = i + 2;//O(n)
    let z = i + 3;//O(n)
  }
  for (let j = 0; j < input; j++) {
    let p = j * 2;//O(n)
    let q = j * 2;//O(n)
  }
  let whoAmI = "I don't know";//O(1)
}

A: Still O (n) –> by rule 2, ignore the Constants part.

example3

function printFirstItemThenFirstHalfThenSayHi100Times(items) {
    console.log(items[0]);

    var middleIndex = Math.floor(items.length / 2);
    var index = 0;

    while (index < middleIndex) {
        console.log(items[index]);
        index++;
    }

    for (var i = 0; i < 100; i++) {
        console.log('hi');
    }
}

A: Still O (n) // O (1+n/2 + 100) –> ignore the constants part, and Iterating through half a collection is still O(n)

example4

const boxes = ['a', 'b', 'c', 'd', 'e'];
function logAllPairsOfArray(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      console.log(array[i], array[j])
    }
  }
}

logAllPairsOfArray(boxes)

A: O ( n ^ 2 ) –> nested loop

example5

function printAllNumbersThenAllPairSums(numbers) {

  console.log('these are the numbers:');
  numbers.forEach(function(number) {
    console.log(number);
  });

  console.log('and these are their sums:');
  numbers.forEach(function(firstNumber) {
    numbers.forEach(function(secondNumber) {
      console.log(firstNumber + secondNumber);
    });
  });
}

printAllNumbersThenAllPairSums([1,2,3,4,5])

A: O (n^2) –> originally should be O (n+n^2), but by rule 4, we keep the dominant part only on the big scale.

example5

'sdfhasdklfjas;dlkfjasd;lkfj'.length // O(1)

The answer to this example actually depends on the language you are using. In JS, “.length” is not looping each letter of the string, so the answer is O (1).

Conclusion

What is a good code? –> Readable and Scalable (speed and Memory) … Higher Speed would take more memory and low usage of memory would result in slow speed. We always need to trade-off, save time or save space.

Knowing how much time your code takes how much memory it uses is very very critical. Those are expensive things for a company or a product. Now big-O is a very important concept that you won’t find in your day-to-day job but it’s something that should always be in the back of your mind and good developers and engineers always have this knowledge. That is why it is such a popular topic during interviews.

Other resources:

What is the difference between big oh, big omega and big theta notations?

Big-O cheat sheet