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