Если кто-то еще работал над той же проблемой, что и вы, и определил, что время выполнения составляет O(n^2), то по определению O(n^3) также связана с той же проблемой. Ваша проблема, если другой человек прав, заключается в том, что предел O(n^3), о котором вы сообщаете, не является самым жестким пределом, который можно дать. На самом деле, это довольно далеко от самой жесткой границы.
В общем, самая жесткая граница - это то, что мы хотим сообщить для алгоритма или времени выполнения, потому что это говорит нам о том, сколько вычислительной мощности нам может понадобиться для решения проблемы. Поэтому вы должны просмотреть свой ответ и попытаться выяснить, можете ли вы получить O(n^2) границы.