0

I keep reading that a function $g(n)$ dominates a function $f(n)$ if there are constants $K$ and $L$ where:

$K \cdot g(n) \ge f(n)$ whenever $n \ge L$

My confusion is in the finding values for those constants. How do you find fitting values to these constants?

In class, I was given the example:

Suppose $g(n) = n^2$ and $f(n) = 7n^2 + 5n$ choose $K = 8$ and $L = 6$

See Table

It is now clear that $g(n)$ dominates $f(n)$ Note: $f(n)$ dominates $g(n)$ when $K \le 7$ thus, the two functions are equivalent

There is no equations or context given as to how $8$ and $6$ were chosen to represent $K$ and $L$, respectively. What decided those values? Why should $8$ and $6$ be chosen, as opposed to any pair of numbers like $-3$ and $12$ or $19.6$ and $\pi$?

FShrike
  • 40,125
FoxVocs
  • 3
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Sep 02 '21 at 20:49
  • Please use mathjax - I have edited this in for you. At its most basic, all you need to do is append dollar signs $ so that $n^2$ looks like $n^2$ – FShrike Sep 02 '21 at 21:34
  • Welcome. For the record, the comment section on this site is not for answers, so being exasperated when the comment does not answer your question is ... pointless, and may attract dislike. As it happens, I am working on an answer for you right now anyway – FShrike Sep 02 '21 at 21:39
  • if you want $K$ to be a natural number then $8$ is the least value such that $f(n)$ dominates $g(n)$ that is because otherwise $7n^2$ would 'nullify your efforts' . You can apply the same logic with $L$ after you know you need $K=8$, you can see all of this just by rearranging the inequality as $(K-7) n^2 \geq 5n$ – Tortar Sep 02 '21 at 21:43
  • I'm sorry. I deleted my comment moments after posting. I have been having difficulty in school, and today was one of the worst yet, caused mostly by this problem. I should have been grateful that you were helping me make my question easily understood. – FoxVocs Sep 02 '21 at 21:43
  • It's ok, don't worry. I wasn't upset, just warning you of the sometimes quite strict etiquette expected on this site – FShrike Sep 02 '21 at 21:46

2 Answers2

0

Note 1: it is strange (and I think an abuse of terminology) to say that $f(n)$ dominates $g(n)$ when $K\le7$; this is in contradiction to the definition of domination. Domination occurs (or almost always implies that it occurs) as $n\to\infty$, i.e. for all $n$ larger than a certain point.

Note 2: there are many (infinitely many) such numbers $K,L$. $8,6$ were chosen since they are integers and the example is simple. $8$ is easily decided by the observation $7\cdot g(n)=7n^2\lt f(n)=7n^2+5n$, but $8\cdot g(n)=8n^2\gt7n^2+5n$ when $n$ is beyond a certain point.

You just had to compare coefficients of $n^2$ to find an example $K$, since this is a simple polynomial case. Once you have decided $K$, $L$ is very trivially decided by finding some value $L_1$ where $Kg(L_1)=f(L_1)$, because by definition of $K$ that means $n\gt L_1\implies Kg(n)\gt f(n)$.

We want to find $L_1$ so that:

$$8L_1^2=7L_1^2+5L_1\implies L_1^2=5L\implies L_1=5$$

So any $n\gt L_1$ has $Kg(n)\gt f(n)$. The author of your exercise chose an $L=6\gt5$ for convenience, so now $Kg(n)\gt f(n)$ whenever $n\ge L=6$.

FShrike
  • 40,125
0

Say shortly, one way for "finding values for those constants" comes by solving inequalities from definitions. Down is explanation.

For given functions we can say, that "$g$ dominates $f$", but it's interesting, that also, in your case, "$f$ dominates $g$".

From definition is clear, that we need to solve inequality $$f(n) = 7n^2 + 5n \leqslant K\cdot g(n)=K\cdot n^2 \\ 5n \leqslant (K-7) n^2 \\ 5 \leqslant (K-7) n \\ \frac{5}{K-7 } \leqslant n$$ so, taking any $K>7$ and then any $L\geqslant\left\lfloor \frac{5}{K-7 } \right\rfloor+1$ gives pair $K,L$, which satisfies domination definition.

On other hand lets look to reverse domination: $$g(n) = n^2 \leqslant K\cdot f(n)=K\cdot (7n^2 + 5n)\\ 0 \leqslant (7K-1) n^2 +5Kn\\ $$ to satisfy last equality it's enough to take $7K-1>0$ and any $L\geqslant 1$. So domination here is mutual. Very vital.

And one more: if/when in future you'll dig more, then you find, that your question by fact deals with big-$O$ definition. Both your functions are in same big-$O$ set: $O(n^2)$. Here is possible to add, that using limit type definitions of domination, we have second way for "finding values for those constants".

zkutch
  • 13,410