4 ms·
Can you get rotating an array to run faster than O(n²)?
- jacquesm 17y agoThat had me puzzled for a bit until I realized he meant a square array of n x n elements. I thought he meant a single dimension array when I first saw the title and a part of the post.
- roundsquare 17y agoSo, this problem question isn't very difficult. However, I am interested in more ways to prove lower bounds on complexity. As far as I know, there are a few ways to do this: 1) Time >= Size Of Output (As done here) 2) Time >= Number of bits of information (As in the case of showing that sorting takes O(n*log[n]) if all you can do is compare elements). Are there other ways to find lower bounds?