문제

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