0
$\begingroup$

enter image description here

Here is the video in question:https://www.youtube.com/watch?v=BpiMRyWoDu0&t=131s

F(n) and g(n) are both equal to each other since they both have a time complexity of n^2

What's the point of applying the constant c to g(n) to make it 2n^2? What is this trying to show us?

Additionally, why does the inequality include 'equal to'? When will 2n^2 ever be equal to n^2 + n + 3?

Further more, why has he written n >= 4? Where did the 4 come from? I understand why he wrote n >= 3 because n(n-1)is the same as n for time complexity purposes, therefore this becomes n >= 3

$\endgroup$
1
  • $\begingroup$ "F(n) and g(n) are both equal to each other since they both have a time complexity of n^2" - of course no. Belonging to same set does not imply equality, when there are more then one element. $\endgroup$
    – zkutch
    Apr 20 at 20:03
0
$\begingroup$

Look up the definition of big-O. It states that $f=O(g)\iff \exists c>0:\exists n_0\in\mathbb{N}:\forall n>n_0:f(n)\le cg(n)$

$\endgroup$

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.