HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Combining Predicate Logic and BigO

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
combininglogicpredicatebigoand

Problem

I am a beginner to predicate logic and BigO and am having though time understanding the definition of BigO in terms of predicate logic in the picture attached. I particularly am unable to understand what is meant by n0 in this context. Any help is greatly appreciated.

Solution

What the definition is saying is: $f\in O(g)$ if there's a number $n_0$ such that $f(n)$ is less than some multiple of $g(n)$ (that's where the $c$ comes in) for all $n$ larger than $n_0$. In simple terms, it's saying that $f$ is eventually bounded by some fixed multiple of $g$.

Big-O notation is essentially a simplification describing the ultimate rate of growth of a function. Here we don't care at all if, say, $f(n)$ is bigger than $43\cdot g(n)$ for the first thousand values of $n$: if $f(n)<43\cdot g(n)$ for all the rest (the bigger values of $n$), we've established that a multiple of $g$ is an upper bound on the values of $f$.

Context

StackExchange Computer Science Q#116735, answer score: 2

Revisions (0)

No revisions yet.