Object Oriented Design

Today we’re talking more about big O, and efficiency.

T(n) Name Example
O(1) Constant Adding to the front of a linked list
O(n) Linear Accessing each element of an array
O(n^2) Quadratic Checking duplicates in a list
O(n^3) Cubic Matrix multiplication
O(n^d) Polynomial A bunch of random things
O(log(n)) Logarithmic Binary search
O(nlog(n)) Linearithmic Mergesort, heapsort, quicksort

A representation:


Now we’re talking about the traveling salesman problem.

Data structure Add to front Add to back Add in general Find Remove  
List(ArrayList) O(n) O(1)^ O(n) O(n) O(log(n)) O(n)
LinkedList O(1) O(1) O(n) O(n) Linear  
TreeSet N/A N/A O(log(n)) O(log(n)) O(log(n))  
TreeMap N/A N/A O(log(n)) O(log(n)) O(log(n))  
HashMap N/A N/A O(1)** O(1)** O(1)**  
HashSet N/A N/A O(1)** O(1)** O(1)**  

^ Amortized ** Only when the hashcode function has to disperse properly among the buckets