Big O Notation

Objectives

• Define Time Complexity and Space Complexity
• Evaluate the time complexity and space complexity of different algorithms using Big O Notations

Simple Example

Sum Generated by Looping

type TSumRequest = {
  number: number
}

interface ISumResponse {
  success: boolean;
  result: number;
  timeInMili: number;
}

function generateSumWithLoop(sumRequest: TSumRequest): ISumResponse {
  const t1 = Date.now();
  let total = 0;
  for (let i = 1; i <= sumRequest.number; i++) {
    total += i;
  }
  const t2 = Date.now();
  return {
    success: true,
    result: total,
    timeInMili: t2 - t1,
  };
}

Sum Generated by Math Operation

type TSumRequest = {
  number: number
}

interface ISumResponse {
  success: boolean;
  result: number;
  timeInMili: number;
}

function generateSumWithMultiplication(sumRequest: TSumRequest): ISumResponse {
  const t1 = Date.now();
  const total = (sumRequest.number * (sumRequest.number + 1)) / 2;
  const t2 = Date.now();
  return {
    success: true,
    result: total,
    timeInMili: t2 - t1,
  };
}

In bigger number, you might see the difference in time.

• Sum Generated by Looping: The time execution will increase by the n - number. O(n)
• Sum Generated by Math Operation: The time execution relatively constant. O(1)