Létezik olyan y függvény, amire elég nagy x-ekre O (y (x) ) > y (x)?

Utána kell nézni az ordó jelölésnek:

f(x) = O(g(x)), ha |f(x)| <= Cg(x), ahol C egy alkalmas konstans.

Ha most g(x) = f(x), akkor könnyen találhatunk megfelelő C-ket, tehát az ordó jelölés teljesül.

Egy függvény nagyságrendileg nem tér el önmagától.

Hát mivel rekurzíót adtál meg jó lenne ismerni az y(1)-et. De én adok neki valami értéket: y(1)=1

y(x-1) = (y(x-2)+0)+0 = y(x-i) + 0*i

Legyen i = x - 1

y(1)+0*(x-1) = y(1) = 1 = O(1)

Persze. y(x) = x

| x | <= c*| x |; c = 2 és minden x > 1-re. Tehát y(x) = x = O(x) = O(y(x))