Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing


  • 3 years ago

For big-O complexity equations, how is something like \(\frac{N(N-1)}{2}\) simplifies to just \(O(N^2)\)? I know the constants can be ignored because they are not significant, but when expanded, For complexity equations, how is something like\[\frac{N(N-1)}{2} = \frac{N^2-N)}{2}\] Only the \(2\) is a constant, the other \(N\) is not but why does it end up to only \(O(N^2)\)?

  • This Question is Closed
  1. ktobah
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Look, we have : \[\frac{ N^{2} - N }{ 2 } = \frac{ 1 }{ 2 } N^{2} - \frac{ 1 }{ 2 } N\] So when we talk about the complexity, we usually ignore N because it's very very small than \[N^{2}\] Now we have Complexity equal : \[\frac{ 1 }{ 2 } N^{2}\] So with the O notation, the complexity will be : \[O(N^{2})\] Good luck.

  2. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy