3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't think that this question is about first-order logic at all, he definition just uses the common symbols $\forall, \exists$. Have you checked common resources what the Landau-$\mathcal{O}$ notation means? $\endgroup$ – ttnick Nov 6 '19 at 7:55
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot! Highly appreciated. $\endgroup$ – Dhruv Nov 6 '19 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.