|
|
|
|
|
by thetwiceler
4143 days ago
|
|
The treatment of Big O notation is not only misleading (and poorly conveyed) but wrong in several ways. Big O is an upper bound that does not need to be tight. The table displaying the "limit of N for 1 second (standard processor)" and the accompanying note that the chart will eventually become outdated is manifestly wrong and misleading. Big O ignores constant factors and so no such comparisons can be made. For any particular duration of time (or for any particular number of elements), an algorithm with complexity `O(f(N))` may be faster than one with complexity `O(g(N))` regardless of `f` and `g`. Big O is not something that can obsolesce. Also, it is not necessary that there be a base case for recursion (only well-founded recursion). For instance, the Haskell definition repeat :: a -> [a]
repeat x = x : repeat x
is a recursive definition but it has no base case. Of course, there can also be multiple base cases or other more complicated structures.Saying unconditionally that all operations for a hash set or hash map are O(1) is wrong. Opening quotation in LaTeX is accomplished by "``". I also think that the comparison between the human brain and CPU is completely unjustified. Given that most people could not remember the sequence of results of 32 coin tosses, why shouldn't I say they have no greater than 4 bytes of memory? (For myself, I think the most appropriate unit of memory is "10 seconds of commonly spoken English language"). There are already so many terrific sources for learning algorithms that I don't understand why the author created this book. It is not only inaccurate, but more difficult to understand than other resources I have come across (e.g., Coursera). |
|