Grokking Algorithms An Illustrated Guide For Programmers and Other Curious People
by Aditya Y. Bhargava
12 popular highlights from this book
Key Insights & Memorable Quotes
Below are the most popular and impactful highlights and quotes from Grokking Algorithms An Illustrated Guide For Programmers and Other Curious People:
This is one of the unsolved problems in computer science. There’s no fast known algorithm for it, and some smart people think it’s impossible to have a smart algorithm for this problem.
O(log n) is faster than O(n), and it gets a lot faster once the list of items you’re searching through grows.
It takes a lot of operations for everything except the smallest numbers. Once you’re dealing with 100+ cities, it’s impossible to calculate the answer in time—the Sun will collapse first.
Suppose you want to read the last item in a linked list. You can’t just read it because you don’t know what address it’s at. Instead, you have to go to item #1 to get the address for item #2. Then you have to go to item #2 to get the address for item #3.
Linked lists are great if you’re going to read all the items one at a time: you can read one item, follow the address to the next item, and so on. But if you’re going to keep jumping around, linked lists are terrible.
Arrays are different. You know the address for every item in your array.
Arrays are great if you want to read random elements because you can look up any element in your array instantly.
With a linked list, the elements aren’t next to each other, so you can’t instantly calculate the position of the fifth element in memory—you have to go to the first element to get the address to the second element, then go to the second element to get the address of the third element, and so on until you get to the fifth element.
Question: Why does it take O(n) time to insert an element into an array? Suppose you wanted to insert an element at the beginning of an array. How would you do it? How long would it take?
Every day, you write down everything you spent money on. At the end of the month, you review your expenses and sum up how much you spent. So you have lots of inserts and a few reads. Should you use an array or a list?
What’s better if you want to insert elements in the middle: arrays or lists? With lists, it’s as easy as changing what the previous element points to.
for arrays, you have to shift all the rest of the elements down. And if there’s no space, you might have to copy everything to a new location! Lists are better if you want to insert elements into the middle.
