سؤال

I was going through an algorithms PPT and at one point it was given that the complexity of f(n) = b*n + f((n-1) is O(n^2). My analysis was : f(n) = b*n + f(n-1)

=b*n + b*(n-1) + b*(n-2)...

= c * n

Where C is a constant. Which brings the complexity to O(n). I am pretty sure I am going wrong somewhere. Can someone explain this?

هل كانت مفيدة؟

المحلول

=b*n + b*(n-1) + b*(n-2)...

It will be 'n' summations in this equation, so you can't replace it with C, it will be 'n' of 'n', so n^2

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top