Yes, the fact it's >O(n^k) for all k in [1,2) is why it's not strongly. It's still less than O(n^2).