6. Complexity Analysis

Algorithms

• like a recipe
• concrete steps to solve the problem
• language independent (logic itself)

Complexity Analysis

• Objective Criteria

• time, space
• best, average, worst (always think in worst case!)
• Big O

Be aware of the Complexity

Recognise patterns

Think if you can bring it down

Big O

DROP the constant in front of the N

1. Constant - O(k) (k: constant number)
   : stays the same independently of the size of the problem
2. Linear - O(n) (n: number of items)
   : grows proportional to the size of the problem
   e.g. for loop, linked list- find the item
3. Logarithmic - O(logn)

• random array => cut half => repeat until find the element (Binary Search)
• sorted => increase by one

  let count = 0;
  let limit = 100;
  
  for (let i=0; i<limit; i++) {
    limit /= 2;
    count++;
  }

4. Quadratic - O(n^2)
   : nested for loop
5. N log n - O (nlogn)

   let count = 0;
   let limit = 100;
   
   for (let i=0; i<limit; i++) {
     limit /= 2;
     for (let j=0; j<limit; j++) {
       count++;
     }
   }

   e.g. mergeSort

BAD Time Complexity

6. Exponential - O(2^n)
7. Factorial - O(n!)
   e.g. Queen Problem

Hash Table: O(1) average and amortized case complexity, however it suffers from O(n) worst case time complexity.

• Worst Case

1. If too many elements were hashed into the same key: looking inside this key may take O(n) time.
2. Once a hash table has passed its load balance - it has to rehash [create a new bigger table, and re-insert each element to the table].

• average and amortized case

1. It is very rare that many items will be hashed to the same key [if you chose a good hash function and you don’t have too big load balance.
2. The rehash operation, which is O(n), can at most happen after n/2 ops, which are all assumed O(1): Thus when you sum the average time per op, you get : (n*O(1) + O(n)) / n) = O(1)

REF

www.bigocheatsheet.com/