I’ve never encountered this sort of math stuff before, obviously I know what squared is but I’ve never heard of log. I understand we’re trying to figure out what would be the fastest way to sort through our word but I’m a bit lost.
Log is a confusing concept. It actually can mean slightly different things depending on your “base”, but in computer science we usually mean base 2. With base 2, it means the inverse of squared. So if 4^2 is 16, then log(16) = 4. The important thing to take note of is that log(n) is then of course smaller than n, but (log(n)) * n is larger than n (think log(16) * 16, or 4 * 16, which might be hard to figure in your head, but clearly it’s more than 16).
As for what sort of algorithms result in n * log(n) time, that would take a deeper study of sorting algorithms. They usually involve some slightly tricky implementation to make happen.
2 Likes