0
$\begingroup$

I'm newbie in algorithm time complexity. I had a function, f(n) = 2n2 - 4n. I have to proof that f(n) = O(n2).

We can take it like this:
f(n) = 2n2 - 4n $\le$ 2n2 + n2 $\le$ 3n2

What if I just omit the -4n? Because, 0 is the upper bound of -4n? So, it becomes like:
f(n) = 2n2 - 4n $\le$ 2n2 + 0 $\le$ 2n2

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Nothing bad in it - it is correct. But I'm afraid of your title. $\endgroup$
    – zkutch
    Sep 17, 2022 at 16:33
  • $\begingroup$ @zkutch Would you mind editing? If it is awkward. $\endgroup$
    – Ashraful Alam Shakil
    Sep 17, 2022 at 17:04
  • $\begingroup$ The first argument is unnecessary, 2n²-4n<2n² is enough. (You needn't consider n=0). $\endgroup$
    – Yves Daoust
    Sep 17, 2022 at 17:18
  • $\begingroup$ @Ashraful Alam Shakil, You see, usually, tight we called $\Theta$ type estimation - from this point of view it's hard to say, that $0$ is tight for $-4n$. $\endgroup$
    – zkutch
    Sep 17, 2022 at 17:51

0

Reset to default

Your Answer

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