Gce Model Questions Vol1 2022 Computer Studies Question 50

Practice objective / multiple choice question 50 from the 2022 Gce Model Questions Vol1 Computer Studies examination.

Gce Model Questions Vol1 2022 Computer Studies Objective / Multiple Choice Medium Difficulty
Question 50 GCE_MODEL_QUESTIONS_VOL1 • 2022 • COMPUTER_STUDIES • objective

A loop processes an array of n integers. For each i from 1 to n the loop performs a binary search on the sorted sub‑array of length i, which requires ⌊log₂ i⌋ + 1 comparisons. Derive a closed‑form expression for the total number of comparisons performed by the loop in terms of n, and state the asymptotic time‑complexity using Big‑O notation.

Answer Options

A. C(n) = n + Σ_{k=0}^{⌊log₂ n⌋} k·2^{k} + ⌊log₂ n⌋·(n-2^{⌊log₂ n⌋}+1); asymptotic complexity O(n log n)
B. C(n) = n + Σ_{k=0}^{⌊log₂ n⌋-1} k·2^{k} + ⌊log₂ n⌋·(n-2^{⌊log₂ n⌋}+1); asymptotic complexity O(n²)
C. C(n) = n + Σ_{k=1}^{⌊log₂ n⌋} k·2^{k} + ⌊log₂ n⌋·(n-2^{⌊log₂ n⌋}+1); asymptotic complexity O(n log n)
Correct Answer D. C(n) = n + Σ_{k=0}^{⌊log₂ n⌋-1} k·2^{k} + ⌊log₂ n⌋·(n‑2^{⌊log₂ n⌋}+1); asymptotic complexity O(n log n)
Correct Answer
D
Correct Option:
C(n) = n + Σ_{k=0}^{⌊log₂ n⌋-1} k·2^{k} + ⌊log₂ n⌋·(n‑2^{⌊log₂ n⌋}+1); asymptotic complexity O(n log n)

About This Question

This is Gce Model Questions Vol1 2022 Computer Studies Question 50. It is one of the objective questions from the 2022 Gce Model Questions Vol1 Computer Studies examination.

Difficulty level: Medium .

View More Gce Model Questions Vol1 2022 Computer Studies Questions More Gce Model Questions Vol1 Practice Questions Back to Questions

Master the Exam!

You've seen a preview, but there are thousands more questions plus AI tutor to break down complex solutions.

Unlock Full Access Available for Android & Windows
Chat with Support