إثبات عن طريق التعريفي على أن شكل تكرار فرز الفقاعة هو $ \ أوميغا (n ^ 2) $

Question

شكل تكرار فرز الفقاعة هو $ t (n)= t (n-1) + n- 1 $

كيف يمكنني إثبات الحث على أن هذا هو $ \ أوميغا (n ^ 2) $ ؟

أنا عالق مع $ t (n + 1) \ geq cn ^ 2 + n= n (cn + 1) $

Answer 1

على افتراض $ t (1)= 1 دولار ، يمكنك إظهارها عن طريق التعريفي على أنه $ t (n)= \FRAC {n (n-1)} {2} + 1 $ .

القضية الأساسية هي تافهة منذ $ t (1)= 1=frac {1 \ cdot 0} {2} + 1 $ .

أما بالنسبة للخطوة الاستشارية، ففترض أن المطالبة تحمل ما يصل إلى $ t (n) $ . $ \ ادبت {align *} T (N + 1) &= t (n) + (n + 1) - 1=frac {n (n-1)} {2} + 1 + n \\ &=frac {n ^ 2 -n + 2n} {2} + 1=frac {2} + 1=frac {n (n + 1)} {2} + 1 \\ &=frac {(n + 1) ((n + 1) - 1)} {2} + 1. \ نهاية {محاذاة *} $