It is a measure of how an algorithm responds to a data size.

It classifies performance as input size grows. “O” indicates the order of operation: time scale to perform an operation

Many algorithm and DS have more than an O

  • Inserting
  • Searching
O(1)Constant TimeLooking up a single element in an array
O(log n)LogarrithmicFinding an item is a sorted array with a binary search
O(n)Linear timeSearching an unsorted array for a specific value
O(n log n)Log linearComplex sorting algorithm like heapsort and merge sort
O(n2)QuadraticSimple sorting algorithm like bubble sort