Asymptotic notation (big O)

Thread Starter

asilvester635

Joined Jan 26, 2017
73
Asymptotic notations are a little vague for me at the moment. Here I have a problem that asks me if two equations are equal to each other, and it involves the big O notation. I wrote my question in the image in magenta color.

20170207_165638000_iOS.jpg
 
Last edited by a moderator:

WBahn

Joined Mar 31, 2012
30,055
The constant was not turned into the O.

f(n) = O(g(n))

What this means is that there exists come positive constant c and some value of N such that

f(n) ≤ c · g(n) for all n ≥ N

So if

f(n) = k·h(n) (where k is some constant)

We don't care what the value of k is because we can just pick a larger value of c if needed. As a result, f(n) and k(n) are both equal to O(g(n)). Thus multiplicative constants don't matter and we ignore them.
 
Top