Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
coding_cheat_sheet [2020/07/14 22:00]
127.0.0.1 external edit
coding_cheat_sheet [2020/07/27 02:58] (current)
paul [Time Complexity]
Line 43: Line 43:
  
 From here, we can extrapolate that every level of our mergesort takes n operations to merge. The big-O complexity is therefore n times the number of levels. On the last level, the size of the chunks we're merging is n/2. Before that, it's n/4, before that n/8, etc. all the way to size 1. How many times must you divide n by 2 to get 1? log(n). So we have log(n) levels. Therefore, our total runtime is O(n (work per level) * log(n) (number of levels)), n work. From here, we can extrapolate that every level of our mergesort takes n operations to merge. The big-O complexity is therefore n times the number of levels. On the last level, the size of the chunks we're merging is n/2. Before that, it's n/4, before that n/8, etc. all the way to size 1. How many times must you divide n by 2 to get 1? log(n). So we have log(n) levels. Therefore, our total runtime is O(n (work per level) * log(n) (number of levels)), n work.
- 
- 
-  * Doubly Linked List 
-  * Linked list 
-  * Hash table 
-  * Binary Search Tree 
-  * Set 
-  * List 
-  * LRU Cache 
- 
  
 ==== Hashtable ==== ==== Hashtable ====
  • coding_cheat_sheet.txt
  • Last modified: 2020/07/27 02:58
  • by paul