Datastrukturer och algoritmer - Tidskomplexitet

Jag har en fråga (egentligen två där den andra finns i ett annat inlägg) om tidskomplexitet. Uppgiften jag försöker lösa lyder:

Anta g(n) = 3n^2 + 2n +6. Visa att g(n) = O(n2).

Har fått följande förklarad till mig:
För att visa att g(n) = O(n^2), måste vi visa att det finns en konstant c och en gräns n0 så att g(n) <= c * n^2 för alla n >= n0.

Vi kan välja c = 3 och n0 = 1. Då får vi:

g(n) = 3n^2 + 2n + 6 <= 3 * n^2 ( * ) för alla n >= 1.

Detta visar att g(n) = O(n^2).

Fast på ( * ) raden tycker jag att det borde vara omvänt håll på olikhetstecknet eller tänker jag fel, hur kan man i så fall dra den slutsatsen?

Olikheten (*) är en falsk utsaga för alla n>=1. Så den ska du inte dra några slutsatser ifrån alls. Däremot förväntas du hitta ett c och ett n₀, precis som du säger. Du ska hitta ett andragradspolynom som hela tiden är större än g(n) för alla n>=n₀. Polynomet 3n² duger inte. Det är hela tiden mindre än g(n) för alla n>=1.

Formella beviset av att polynom av grad $n$ alltid begränsas av ett monom av grad $n$ följer från triangelolikheten $|a + b| <|a| +="">$ och att $x^{p} <>$ om $x > 1$ och $p <>$ (eftersom upprepad multiplikation med ett tal med ett tal som är större än $1$ ger ett successivt större tal.

Såtter man ihop de påståendena får man

1. Triangelolikheten

$|p(x)| = |a_n x^n + a_{n - 1}x^{n - 1} + ... + a_1 x + a_0| \leq |a_n| |x|^n + |a_{n - 1}||x|^{n - 1} + ... + |a_1| |x| + |a_0|$

Därefter $x^{p} <>$

$p(x) \leq |a_n| |x|^n + |a_{n - 1}||x|^{n - 1} + ... + |a_1| |x| + |a_0| \leq (|a_n| + |a_{n-1}| + ... |a_1| + |a_0|) |x|^n$

Så ett polynom $p(x)$ av grad $n$ är alltid mindre än $C x^n$ om $C$ är summan av absolutbeloppen hos koefficienterna (om x > 1)

Svara