So I'm trying to understand a solution made by my teacher for a question that asks me to determine whether the following is true. I'm having trouble understanding where some values in the steps are coming from.

Like for the first part, I don't really get where n≥5 came from. My guess is getting 16n^2 + 25 to equal 16n^2 + n^2 by substituting n with 5. But I was wondering why 25 turned into n^2 in the first place?

I also have no idea where k = 5 came from.

For the second part of the solution, I'm also having similar struggles. Why did 16n^2 turn into 15n^2 + n^2? I'm also not sure where n≥41 and k=41 came from. I would really appreciate some clarification because I'm having trouble understanding this unit.

enter image description here


Intuitively, for all the notations in this family we only care what happens when $n$ is large. We can ignore any behavior when $n$ is small. Your teacher is choosing the breakpoint where the limiting behavior sets in. S/he wants to say that for $n$ large enough $25 \le n^2$ because that is needed for the argument. This is true as long as $n \ge 5$, which is where it comes from. S/he could have said $n \ge 10$ because there is no need to make the breakpoint as small as possible. You just need the argument to go through for all the $n$ above it.

The point of turning the $25$ into $n^2$ is to get the right side to be proportional to $n^2$ so you can invoke the definition of $O(n^2)$. We say that $f(n)\in O(n^2)$ as long as $f(n) \le cn^2$ for some fixed $c$ and $n$ large enough. The demonstration shows this works for $c=17$ as long as $n \ge 5$

Your teacher is being careful to follow the definition and show all the steps. Later on you will just say that any terms of lower order than the leading one can be ignored, so once you have $16n^2-40n+25$ you will say this is in $O(n^2)$ immediately

  • $\begingroup$ Hi! So you mentioned getting k from f(n) ≤ kn^2. Is that referring to 16n^2 - 40n + 25 ≤ kn^2? Because I plugged in n = 5 which gave me 225 ≤ k(5)^2 and when I plugged in the teacher's value of k = 5, I got 225 ≤ 125. That doesn't seem right to me, I think I'm misunderstanding something. $\endgroup$ – Blackthorn Jun 9 '19 at 22:31
  • 1
    $\begingroup$ Sorry, it should be $cn^2$. I got myself confused between $c$ and $k$. With $c=17$ you have $225 \le 17\cdot 5^2=425$, which is true. $\endgroup$ – Ross Millikan Jun 9 '19 at 22:39
  • $\begingroup$ But I'm confused as to where I would figure out the value of k since theres no formula? Where did the teacher get k = 5 from? $\endgroup$ – Blackthorn Jun 9 '19 at 22:41
  • $\begingroup$ S/he wanted $25 \le n^2$ and derived $k=5$ from that. That allowed the statement $16n^2+25 \le 17n^2$. That is true for any $n \ge 5$. $\endgroup$ – Ross Millikan Jun 9 '19 at 22:43
  • $\begingroup$ So would k just be equal to whatever n is? $\endgroup$ – Blackthorn Jun 9 '19 at 23:04

We say $f(x)=O(g(x)),$ if there exists a $k \in \mathbb{N}$ and $c \in \mathbb{R}$, s.t. for any $n\geq k$, we have $f(n)\leq c g(n)$.

for the first one, whenever $n \geq 5$, we have $5^2\leq n^2$, which gives $16n^2+25 \leq 16n^2+n^2=17n^2$, as stated by your professor. He chose $k=5$ and $c=17$, and whenever $n \geq$5, we have $f(n)\leq 17g(n) $, so by defintion $f(x)=O(g(x))$

Similarly, we say $f(x)=\Omega(g(x)),$ if there exists a $k \in \mathbb{N}$ and $c \in \mathbb{R}$, s.t. for any $n\geq k$, we have $f(n)\geq c g(n)$.

Then $f(n)=16n^2-40n+15 \geq 16n^2-40n=15n^2+n^2-40n \geq n^2-40n$ (this is because $15n^2 \geq 0$). Therefore $f(n)\geq n^2-40n=n(n-40)$. $n$ is always non-negative, therefore $f(n)$ being the product of $n$ and $n-40$ is guaranteed to be positive as long as $n-40>0$, is as long as $n\geq 41$.

Therefore $f(n)=15n^2+n^2-40n+25\geq15n^2+n^2-40n$, and $n^2-40n$ is non-negative as long as $n>41$. So for any $n>41$, we have $f(n)\geq 15n^2$, so for $c=15$, and $k=41$, we have $f(n) \geq15g(n)$, so by definition $f(n)=\Omega(n^2)$.

Put everything together to conclude that $f(n)=\Theta(n^2)$.


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.