Zasoby, które znalazłem na temat złożoności czasowej, nie są jasne, kiedy można zignorować terminy w równaniu złożoności czasowej, w szczególności na przykładach innych niż wielomianowe.
Jest dla mnie jasne, że biorąc pod uwagę coś w formie n 2 + n + 1, ostatnie dwa terminy są nieistotne.
W szczególności, biorąc pod uwagę dwie kategorie, 2 n i n * (2 n ), czy druga jest w tej samej kolejności co pierwsza? Czy dodatkowe mnożenie tam ma znaczenie? Zwykle zasoby po prostu mówią, że x n ma charakter wykładniczy i rośnie znacznie szybciej ... a następnie iść dalej.
Rozumiem, dlaczego tak się nie stanie, ponieważ 2 n znacznie przewyższy n, ale ponieważ nie są one sumowane razem, będzie to miało duże znaczenie przy porównywaniu dwóch równań, w rzeczywistości różnica między nimi zawsze będzie czynnikiem n, co wydaje się co najmniej ważne.
n! = o((n+1)!)
rośnie asymptotycznie ściśle wolniej.