mikeizbicki
commented
2 months ago Your basic logic is correct, but the following statement is incorrect:
n^(2.1) < n^(2)*log(n) for n > 23
See for example: https://www.wolframalpha.com/input?i=lim+n-%3Einf+n+log%28n%29+%2F+n%5E2.1
It is the case that polynomials (even very small ones) are always bigger than logarithms in the limit. Therefore $n^{2.1}$ sits in the intermediate range between $n^2\log n$ and $n^{2.3...}$.
Aside:
This is a fantastic question, and it was asked in a great professional way with helpful pictures for context. Well written questions like this make responding to them a pleasure and make other people (e.g. future hiring managers) want to work with you. The only way the question could be slightly improved is using latex notation within dollar signs to format the math a bit nicer (e.g. $n^2\log n$ displays as $n^2 \log n$ ).
Can someone explain why 9 is Open?
Intuitively it makes sense that it is open as there could technically be a faster algo. After all, we know for sure that it will take at least Omega(n^2) because the resulting matrix is nxn. But I am tripped off by the fact that n^(2.1) < n^(2)*log(n) for n > 23.