Author: Cibin K.Thankachan

Arrays

BIG(O)

Time and space complexity analysis

Linear time

O(1) – accessing array by index

O(log n) – example : binary search

O(N) – finding an item in an unsorted list

O(NLog N) – Merge sort or quick sort, often seen in divide and conquer algorithms

O(N^2) – Quadratic, usually seen in bubble sort and selection sort . Each element needs to be compared to every another element such as nested loops.

O(2^N) – exponential, time taken doubles with each addition to N and rapidly growing execution times. Example : finding all subsets in a set.

O(N!) – factorial example is solving the travelling salesman problem, extremely slow execution times