# Concept derivation guides

299 concept teaching guides, separate from the 36,000 individual question derivations.

[Search all questions & derivations →](/en/explore/)

1 1 results · Page 1 of 1



Concept guide



## [Asymptotic resource bounds: proving 3n²+5n+2∈Θ(n²) and ruling out Θ(n)](/en/derivations/derivation-mko-asymptotic-resource-bound-01/?from=%2Fen%2Fderivations%2F%3Fq%3Dmko-asymptotic-resource-bound)

Let the cost function be f(n)=3n²+5n+2 (n starting at 0), with comparison functions g(n)=n² and h(n)=n. With explicit full-tail witnesses prove f∈O(g) (c=10, N=1) and f∈Ω(g) (c=3, N=0), hence f∈Θ(g); show that N=0 cannot work for O, that c=3 cannot work for O, and that another witness c=4, N=6 also works; then prove f∉O(h), so f∈Ω(h) but f∉Θ(h).

Asymptotic resource bounds

derivation-mko-asymptotic-resource-bound-01





1 1 results · Page 1 of 1