- Published on
CS 3500 Day 14
- Authors
- Name
- Jacob Aronoff
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