Истина или ложь: алгоритм O (n ^ 3) будет работать быстрее, чем алгоритм O (n ^ 4) для достаточно большого n

Question

Я немного смущен тем, как решить этот вопрос. Мой инстинкт заключается в том, что утверждение верно при отображении n ^ 3 и n ^ 4. Однако при применении констант, например, 100n ^ 3, утверждение ложно. Как бы я пришел к этому вопросу?

Answer 1

Если они используют неформальное определение (которое действительно является большой тэтой), тогда ответ, очевидно, да.

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