2019-01-02

CS: Asymptotic notation

Omicron or Big-O (Ο)

The Big-O sets the upper limit of a given function f(n). The set of functions Ο(g(n)) is all f(n) functions defined by:

9321e17836700f7c25ebd23db9b51dfe.png

Which basically means that, given n0, c * g(n) it’s always greater equals than f(n). It’s supposed to be it’s upper limit. To demostrate that a given function is in the set of functions of Ο(g(n)):

5350bb29b0ba717c96295c82fc4fc543.png

It will be neccessary to find any pair of values for c > 0 and n0 > 0 in order to prove that:

328a1ed3bc1940174402e61384cfcb63.png
Demostrate that 6n + 2 ∈ Ο(n)
— example

  • Step 1: To find the right c constant

  • Step 2: To find n > 0 so that 6n + 2 ≤ cn

  • It’s enough to find two possible values. For instance, a possible solution could be: c = 6 it’s valid for all n ≥ 2, therefore we can use n0 = 2

Omega (Ω)

TODO

Theta (ϴ)

TODO

Resources