# Differences

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

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