5 ms·
Tangential question: How can an algorithm end up with a fractional exponent? It's clear to me how nested loops can give O(n^2) or O(n^2), and how a binary searc
by AdamH12113 3y ago
Tangential question: How can an algorithm end up with a fractional exponent? It's clear to me how nested loops can give O(n^2) or O(n^2), and how a binary search can give O(log n), but how on earth can you get something like O(n^2.371552), or even O(n^2.7)?
- vman512 3y agoIt's pretty easy to get to O(N^(3/2)) at least, since that is sqrt(N)^3 Imagine an algorithm that re-arranges a list into a sqrt(N) by sqrt(N) grid, and does O(num_columns^2) work for each row.
- jcranmer 3y agoThe classic example here is Strassen's algorithm. You divide your two input matrices into quarters, and then you need to do 7 matrix multiplies of the smaller (n/2) matrices. When you add up the total work done, this ends up needing to do n^(log base 2 of 7) work, or about n^2.8.
- csjh 3y agoMany divide and conquer algorithms are expressed in the form O(n^logb(a)) because of the master theorem https://en.m.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms) https://en.m.wikipedia.org/wiki/Master_theorem_(analysis_of_...
- kzrdude 3y agoI think a simpler algorithm like https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm demonstrates how it can happen.