BigO

~~Big O
~~Question:
Depth First Search (DFS)
~Answer:
Graph of |V| vertices and |E| edges
Average Time Complexity: - 
Worst Time Complexity: (Good) O(|E| + |V|)
Worst Space Complexity: O(|V|)


~~Question:
Breadth First Search (BFS)
~Answer:
Graph of |V| vertices and |E| edges
Average Time Complexity: -
Worst Time Complexity: O(|E| + |V|)
Worst Space Complexity: O(|V|)

~~Question:
Binary Search
~Answer:
Sorted array of n elements
Average Time Complexity: (Good) O(log(n))
Worst Time Complexity: (Good) O(log(n))
Worst Space Complexity: O(1)

~~Question:
Linear (Brute Force)
~Answer:
Array
Average Time Complexity: (Bad) O(n)
Worst Time Complexity: (Bad) O(n)
Worst Space Complexity: O(1)

~~Question:
Shortest Path by Djikstra,
Using Min-Heap as a priority Queue
~Answer:
Graph with |V| vertices and |E| edges
Average Time Complexity: (Fair) O((|V| + |E|) log |V|)
Worst Time Complexity: (Fair) O((|V| + |E|) log |V|)
Worst Space Complexity: (Fair) O(|V|)

~~Question:
Shortest path by Dijkstra,
Using an unsorted array as priority queue
~Answer:
Graph with |V| vertices and |E| edges
Average Time Complexity: (Fair) O(|V|^2)
Worst Time Complexity: (Fair) O(|V|^2)
Worst Space Complexity: (Fair) O(|V|)

~~Question:
Shortest path by Bellman-Ford
~Answer:
Graph with |V| vertices and |E| edges
Average Time Complexity: (Fair) O(|V||E|)
Worst Time Complexity: (Fair) O(|V||E|)
Worst Space Complexity: (Fair) O(|V|)

~~Question:
Quick Sort
~Answer:
Array

Best Time: (Fair) O(n log(n))
Average Time: (Good) O(n log(n))
Worst Time: (Bad) O(n^2)
Worst Case Aux.: O(n)

~~Question:
Merge Sort
~Answer:
![alt text](http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif "Merge Sort")
Array

Best Time: (Fair) O(n log(n))
Average Time: (Good) O(n log(n))
Worst Time: (Good) O(n log(n))
Worst Case Aux.: (Bad) O(n)

~~Question:
Heap Sort
~Answer:
Array
![alt text](http://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif "Heap Sort")

Best Time: (Fair) O(n log(n))
Average Time: (Good) O(n log(n))
Worst Time: (Good) O(n log(n))
Worst Case Aux.: (Good) O(1)

~~Question:
Bubble Sort
~Answer:
Array
![alt text](http://upload.wikimedia.org/wikipedia/commons/5/54/Sorting_bubblesort_anim.gif "Bubble Sort")

Best Time: (Good) O(n)
Average Time: (Bad) O(n^2)
Worst Time: (Bad) O(n^2)
Worst Case Aux.: (Good) O(1)

~~Question:
Insertion Sort
~Answer:
Array
![alt text](http://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif "Insertion Sort")

Best Time: (Good) O(n)
Average Time: (Bad) O(n^2)
Worst Time: (Bad) O(n^2)
Worst Case Aux.: (Good) O(1)

~~Question:
Selection Sort
~Answer:
Array
![alt text](http://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif "Selection Sort")

Best Time: (Bad) O(n^2)
Average Time: (Bad) O(n^2)
Worst Time: (Bad) O(n^2)
Worst Case Aux.: (Good) O(1)

~~Question:
Bucket Sort 
~Answer:
Array
1. Set up an array of initially empty "buckets".
2. Scatter: Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array.
![alt text](http://upload.wikimedia.org/wikipedia/commons/6/61/Bucket_sort_1.png "Bucket Sort")

Best Time: (Good) O(n+k)
Average Time: (Good) O(n+k)
Worst Time: (Bad) O(n^2)
Worst Case Aux.: (Fair) O(nk)

~~Question:
Radix Sort
~Answer:
Array

Best Time: (Good) O(nk)
Average Time: (Good) O(nk)
Worst Time: (Good) O(nk)
Worst Case Aux.:  (Fair) O(nk)

![alt text](http://upload.wikimedia.org/wikipedia/commons/6/61/Bucket_sort_1.png "Bucket Sort")

~~Question:
Data Structure: Basic Array
~Answer:
Avg. Case Index: (Good) O(1)
Avg. Case Search: (Bad) O(n)
Avg. Case Insertion: -
Avg. Case Deletion: - 
Worst Case Index: (Good) O(1)
Worst Case Search: (Bad) O(n)
Worst Case Insertion: -
Worst Case Deletion: -

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: Dynamic Array
~Answer:
Array resizes
Avg. Case Index: (Good) O(1)
Avg. Case Search: (Bad) O(n)
Avg. Case Insertion: (Bad) O(n)
Avg. Case Deletion: (Bad) O(n)
Worst Case Index: (Good) O(1)
Worst Case Search: (Bad) O(n)
Worst Case Insertion: (Bad) O(n)
Worst Case Deletion: (Bad) O(n)

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: Singly-Linked List
~Answer:
Avg. Case Index: (Bad) O(n)
Avg. Case Search: (Bad) O(n)
Avg. Case Insertion: (Good) O(1)
Avg. Case Deletion: (Good) O(1)
Worst Case Index: (Bad) O(n)
Worst Case Search: (Bad) O(n)
Worst Case Insertion: (Good) O(1)
Worst Case Deletion: (Good) O(1)

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: Doubly-Linked List
~Answer:
Avg. Case Index: (Bad) O(n)
Avg. Case Search: (Bad) O(n)
Avg. Case Insertion: (Good) O(1)
Avg. Case Deletion: (Good) O(1)
Worst Case Index: (Bad) O(n)
Worst Case Search: (Bad) O(n)
Worst Case Insertion: (Good) O(1)
Worst Case Deletion: (Good) O(1)

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: Skip List
~Answer:
Avg. Case Index: (Fair) O(log(n))
Avg. Case Search: (Good) O(log(n))
Avg. Case Insertion: (Good) O(log(n))
Avg. Case Deletion: (Good) O(log(n))
Worst Case Index: (Bad) O(n)
Worst Case Search: (Bad) O(n)
Worst Case Insertion: (Bad) O(n)
Worst Case Deletion: (Bad) O(n)

Space Complexity: (Bad) O(log(n))

~~Question:
Data Structure: Hash Table
~Answer:
Avg. Case Index: -
Avg. Case Search: (Good) O(1)
Avg. Case Insertion: (Good) O(1)
Avg. Case Deletion: (Good) O(1)
Worst Case Index: -
Worst Case Search: (Bad) O(n)
Worst Case Insertion: (Bad) O(n)
Worst Case Deletion: (Bad) O(n)

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: Binary Search Tree
~Answer:
Avg. Case Index: (Fair) O(log(n))
Avg. Case Search: (Good) O(log(n))
Avg. Case Insertion: (Good) O(log(n))
Avg. Case Deletion: (Good) O(log(n))
Worst Case Index: (Bad) O(n)
Worst Case Search: (Bad) O(n)
Worst Case Insertion: (Bad) O(n)
Worst Case Deletion: (Bad) O(n)

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: Cartesian Tree
~Answer:
Avg. Case Index: -
Avg. Case Search: (Good) O(log(n))
Avg. Case Insertion: (Good) O(log(n))
Avg. Case Deletion: (Good) O(log(n))
Worst Case Index: -
Worst Case Search: (Bad) O(n)
Worst Case Insertion: (Bad) O(n)
Worst Case Deletion: (Bad) O(n)

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: B-Tree
~Answer:
Avg. Case Index: (Fair) O(log(n))
Avg. Case Search: (Good) O(log(n))
Avg. Case Insertion: (Good) O(log(n))
Avg. Case Deletion: (Good) O(log(n))
Worst Case Index:  (Fair) O(log(n))
Worst Case Search: (Good) O(log(n))
Worst Case Insertion: (Good) O(log(n))
Worst Case Deletion: (Good) O(log(n))

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: Red-Black-Tree
~Answer:
Avg. Case Index: (Fair) O(log(n))
Avg. Case Search: (Good) O(log(n))
Avg. Case Insertion: (Good) O(log(n))
Avg. Case Deletion: (Good) O(log(n))
Worst Case Index:  (Fair) O(log(n))
Worst Case Search: (Good) O(log(n))
Worst Case Insertion: (Good) O(log(n))
Worst Case Deletion: (Good) O(log(n))

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: Splay Tree
~Answer:
Avg. Case Index: -
Avg. Case Search: (Good) O(log(n))
Avg. Case Insertion: (Good) O(log(n))
Avg. Case Deletion: (Good) O(log(n))
Worst Case Index:  -
Worst Case Search: (Good) O(log(n))
Worst Case Insertion: (Good) O(log(n))
Worst Case Deletion: (Good) O(log(n))

Space Complexity: (Fair) O(n)

~~Question:
Data Structure: AVL Tree
~Answer:
Avg. Case Index: -
Avg. Case Search: (Good) O(log(n))
Avg. Case Insertion: (Good) O(log(n))
Avg. Case Deletion: (Good) O(log(n))
Worst Case Index:  -
Worst Case Search: (Good) O(log(n))
Worst Case Insertion: (Good) O(log(n))
Worst Case Deletion: (Good) O(log(n))

Space Complexity: (Fair) O(n)

~~Question:
Linked List (Sorted) Heap
~Answer:
Heapify: - 
Find Max: (Good) O(1)
Extract Max: (Good) O(1)
Increase Key:  (Bad) O(n)
Insert:  (Bad) O(n)
Delete:  (Good) O(1)
Merge: (Bad) O(m+n)


~~Question:
Linked List (Unsorted) Heap
~Answer:
Heapify: - 
Find Max: (Bad) O(n)
Extract Max: (Bad) O(n)
Increase Key:  (Good) O(1)
Insert:  (Good) O(1)
Delete:  (Good) O(1)
Merge:  (Good) O(1)

~~Question:
Binary Heap
~Answer:
Heapify: (Fair) O(n)
Find Max: (Good) O(1)
Extract Max: (Fair) O(log(n))
Increase Key:  (Fair) O(log(n))
Insert:  (Fair) O(log(n))
Delete:  (Fair) O(log(n))
Merge:  (Bad) O(m+n)

~~Question:
Binomial Heap
~Answer:
Heapify: -
Find Max: (Fair) O(log(n))
Extract Max: (Fair) O(log(n))
Increase Key:  (Fair) O(log(n))
Insert:  (Fair) O(log(n))
Delete:  (Fair) O(log(n))
Merge:  (Fair) O(log(n))

~~Question:
Fibbonaci Heap
~Answer:
Heapify: -
Find Max: (Good) O(1)
Extract Max: (Fair) O(log(n))*
Increase Key:  (Good) O(1)*
Insert:  (Good) O(1)
Delete:  (Fair) O(log(n))*
Merge:  (Good) O(1)

~~Question:
Adjacency List
~Answer:
Storage:  (Fair) O(|V|+|E|)
Add Vertex:  (Good) O(1)
Add Edge:  (Good) O(1)
Remove Vertex:  (Fair) O(|V|+|E|)
Remove Edge:  (Fair) O(|E|)
Query:  (Fair) O(|V|)

~~Question:
Incidence List
~Answer:
Storage:  (Fair) O(|V|+|E|)
Add Vertex:  (Good) O(1)
Add Edge:  (Good) O(1)
Remove Vertex:  (Fair) O(|E|)
Remove Edge:  (Fair) O(|E|)
Query:  (Fair) O(|E|)

~~Question:
Adjacency Matrix
~Answer:
Storage:  (Bad) O(|V|^2)
Add Vertex:  (Bad) O(|V|^2)
Add Edge:  (Good) O(1)
Remove Vertex:  (Bad) O(|V|^2)
Remove Edge:  (Good) O(1)
Query:  (Good) O(1)

~~Question:
Incidence Matrix
~Answer:
Storage:  (Bad) O(|V|⋅|E|)
Add Vertex:  (Bad) O(|V|⋅|E|)
Add Edge:  (Bad) O(|V|⋅|E|)
Remove Vertex:  (Bad) O(|V|⋅|E|)
Remove Edge:  (Bad) O(|V|⋅|E|)
Query:  (Good) O(|E|)