तीन की asymptotic विश्लेषण छोरों

Question

के लिए नेस्ट मैं पाश के लिए इस नेस्टेड की थीटा जटिलता गणना करना चाहते हैं:

for (int i = 0; i < n; i++) { 
     for (int j = 0; j < i; j++) { 
      for (int k = 0; k < j; k++) { 
       // statement 

मैं इसे n^3 का कहना है कि चाहते हैं, लेकिन मुझे नहीं लगता कि यह सही है, क्योंकि लूप के लिए प्रत्येक 1 से एन तक नहीं जाता है। मैं कुछ परीक्षण किया:

एन = 5 -> 10

10 -> 120

30 -> 4060

50 -> 19600

तो यह एन के बीच होना चाहिए^2 और एन^3। मैंने संक्षेप सूत्र और इस तरह की कोशिश की, लेकिन मेरे परिणाम बहुत अधिक हैं। एन^2 लॉग (एन) के बावजूद, लेकिन यह भी गलत है ...

Answer 1

यह O(N^3) है। सटीक सूत्र (N*(N+1)*(N+2))/6

Answer 2

है सिग्मा अंकन का उपयोग कदम पद्धति द्वारा एक कुशल कदम है: