Javascript Algorithm implementation of MIT Course Number 6.006
Algorithm Time & Space complexity
| Data Structure | Time Complexity | Space Complexity | |||
|---|---|---|---|---|---|
| Worst | Worst | ||||
| Access | Search | Insertion | Deletion | ||
| Array | O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| Stack | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Queue | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Singly-Linked List | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Doubly-Linked List | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Hash Table | N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| Binary Search Tree | O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| B-Tree | O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| AVL Tree | O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Array Sorting Algorithms | |||||
| Quicksort | Ω(n log(n)) / O(n^2) |
O(log(n)) |
|||
| Mergesort | O(n log(n)) |
O(n) |
|||
| Counting Sort | O(n+k) |
O(k) |
|||
| Selection Sort | O(n^2) |
O(1) |
|||
| Heapsort | O(n log(n)) |
O(1) |
|||
| Graph Algorithms | |||||
| Tree traversal | O(N + N-1) |
O(N) |
|||
| Dijkstra | O(E+VlogV) |
O(V^2) |
|||
| Breadth first search | O(E+V) |
O(V) |
|||
| Depth first search | O(E+V) |
O(V) |
|||
| Bellman Ford | O(EV) |
O(V) |
|||
- Lecture 1: Algorithmic Thinking, Peak Finding
- Lecture 2: Models of Computation, Document Distance
- Lecture 3: Insertion Sort, Merge Sort
- Lecture 4: Heaps and Heap Sort
- Lecture 5: Binary Search Trees, BST Sort
- Lecture 6: AVL Trees, AVL Sort
- Lecture 7: Counting Sort, Radix Sort, Lower Bounds for Sorting
- Lecture 8: Hashing with Chaining
- Lecture 9: Table Doubling, Karp-Rabin
- Lecture 10: Open Addressing, Cryptographic Hashing
- Lecture 11: Integer Arithmetic, Karatsuba Multiplication
- karatsuba.js - Karatsuba multiplication algorithm
- Lecture 12: Square Roots, Newton's Method
- Lecture 13: Breadth-First Search (BFS)
- breadth_first_search.js
- breadth_first_search_queue.js - with an Queue Classes
- breadth_first_search_traversal.js
- Lecture 14: Depth-First Search (DFS), Topological Sort
- Lecture 15: Single-Source Shortest Paths Problem
- Unweighted, undirected graph.js
- Lecture 16: Dijkstra
- Lecture 17: Bellman-Ford
- Lecture 18: Speeding up Dijkstra
- Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths
- Lecture 20: Dynamic Programming II: Text Justification, Blackjack
- Lecture 21: Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
- Lecture 22: Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
- Lecture 23: Computational Complexity
- Lecture 24: Topics in Algorithms Research