मज़ा की समय जटिलता()?

Question

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

int fun(int n) 
{ 
    int count = 0; 
    for (int i = n; i > 0; i /= 2) 
    for (int j = 0; j < i; j++) 
     count += 1; 
    return count; 
} 

मेरी पहली छाप हे (एन एन लॉग इन करें) था, लेकिन इस सवाल का जवाब हे (एन) है। कृपया मुझे समझने में सहायता करें कि यह ओ (एन) क्यों है।

Answer 1

भीतरी पाश n पुनरावृत्तियों, तो n/2, तो n/4, आदि तो भीतरी पाश पुनरावृत्तियों की कुल संख्या है करता है:

n + n/2 + n/4 + n/8 + ... + 1 
<= n * (1 + 1/2 + 1/4 + 1/8 + ...) 
= 2n 

(Geometric series देखें), और इसलिए हे (एन) है।