Question
1.
2.
3.
4.
Answer (Detailed Solution Below)
Option 2 : $O(n)$
Advertisement
Detailed Solution
सही उत्तर $O(n)$ है।
Key Points
Helpful?
prepsnap.in • Part -AQuestion:
What is the time complexity of the following code fragment? for (i = 1; i <= n; i = i * 2) for (j = 1; j <= i; j++) // $O(1)$ work / निम्नलिखित कोड खंड की समय जटिलता क्या है? for (i = 1; i <= n; i = i * 2) for (j = 1; j <= i; j++) // $O(1)$ कार्य
1.
$O(\log n)$
2.
$O(n)$
3.
$O(n \log n)$
4.
$O(n^2)$
Correct Answer: $O(n)$
The inner loop runs 1 + 2 + 4 + ... + $2^{\lfloor \log_2 n \rfloor}$ times, a geometric series summing to less than $2n$, so the total work is $O(n)$. / आंतरिक लूप 1 + 2 + 4 + ... + $2^{\lfloor \log_2 n \rfloor}$ बार चलता है, यह गुणोत्तर श्रेणी $2n$ से कम का योग देती है, अतः कुल कार्य $O(n)$ है।
Downloaded from PrepSnap (prepsnap.in)