The video does explain a few basic procedural and technical ideas, which are important, but I don’t think you get the big picture from it. The big picture is this:
Take the task of searching a database. The worst algorithms are generally O(n); the best are generally O(log n). Let me explain the practical significance.
For O(n):
If it takes 1 second to search a thousand records, then it takes a million seconds to search a million records, and it takes 100 million seconds to search a 100 million records. Simple, huh?
But that’s disastrous. If you’re developing a database to check 100 million credit records, then a search time of 100 million seconds is beyond horrible. It would mean that to access John Smith’s credit report, the retrieval time would be thousands of hours. That is absolutely unacceptable.
For O(log n):
But now we have a different situation. O(log n) means that search time increases as the inverse of exponentiation… Exponentiation is fast, explosive. Logarithms, therefore, are the absolute opposite. It means that as N increases exponentially, Log N increases very very slowly. So……
IF it takes 1 second to search a thousand records, THEN
It takes 2 sconds to search a million records,
It takes 3 second to search a billion records,
And it takes 4 seconds to seach a trillion records.
Let’s say that we “only” need to search a billion records. Because of logarithmic growth in the time required, this means that N may grow exponentially while time required increases slowly — in linear amounts.
So insted of needing thousands of hours, we need only 3 seconds for a Database search.
Yet the situation is in some sense better than that. Increases in time required from 1 to 3 to 5 seconds are usually easy for the engineers to handle. Remember that chips are getting faster all the time, a la Moore’s law. So if something takes 5 seconds today, we can expect execution to someday take < 1 second.
That being the case, we can eventually expect a trillion-record search to be very responsive. Some day we should expect access time to easily be 5 times faster, thanks to Moore’s Law. That’s easy.
With the combined virtues of Moore’s Law, along with logmarithmic growth in search time — which is what O(log n) menas — the ability to search literally astronomical numbers of records in less than a second becomes doable.