1

How does $\frac{n(k^2-1)}{2}$ become $nk^2$? I'm sorry for the stupid question but I'm at wits end and I have no idea how to go about this. Context

Thanks

Community
  • 1
user149551
  • 11
  • Please share the background – lab bhattacharjee May 12 '14 at 13:46
  • I'm trying to digest this post http://stackoverflow.com/questions/11026219/why-is-k-way-merge-onk2 – user149551 May 12 '14 at 13:47
  • 2
    In that case, for complexity analysis, one disregards constants ($\frac{1}{2}$) and lower order terms, so $$n\frac{k^2-1}{2} = \frac{1}{2}nk^2 -\frac{1}{2}n$$ reduces to the complexity class $nk^2$. That doesn't mean the values are the same. – Daniel Fischer May 12 '14 at 13:50
  • OH so you're saying that we just ended up disregarding the constants and the lower order terms and that nk2 isn't the simplified value? thank you so much I completely forgot about the definition of asymptotic analysis.... – user149551 May 12 '14 at 14:02
  • 1
    Yeah, just take $n = k = 1$ to realize that they aren't the same. – fuglede May 12 '14 at 14:23

0 Answers0