حل التكرار باستخدام الطريقة الرئيسية

Question

أحاول حل علاقة تكرار لمعرفة تعقيد خوارزمية كتبت.هذه هي المعادلة ..

t (n)= t (n-1) + θ (n)

اكتشفت الإجابة على O (N2)، لكنني لست متأكدا مما إذا فعلت ذلك بشكل صحيح.يمكن لشخص يرجى تأكيد؟

تحديث: ماذا لو كانت المعادلة T (n)= t (n-1) + θ (nlogn)؟هل ستظل س (N2)؟

Answer 1

It is O(N)+O(N-1)+...+O(1) = O(N*(N+1)/2). So yes, the total complexity is quadratic.

Answer 2

Yes, you guess it right.

However, the form of the recurrence doesn't fit with Master method. Since you have guessed the bound correctly, substitution method is more suitable here.

Now your job is finding two constants c and n0 to prove that:

T(n) <= c*(n^2) forall n >= n0