CS 3500 Day 14

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))
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