FPSC- Programmer (BS-17) - Pakistan Meteorological Department (PMD) Model Papers - 2026 — Part 4 (100 Q)

Correct Answer: D. O(log n)
Explanation: Each comparison halves the remaining search space.

Correct Answer: B. O(n log n)
Explanation: The outer loop runs n times, and the inner loop doubles j each time, so it runs log n times.

Correct Answer: D. O(n)
Explanation: The total work is 1 + 2 + 4 + ... + (a value less than n), which is less than 2n. Multiplying the loop counts (log n × n) overestimates it. ALSO KNOW (related points): • What is the worst-case time complexity of binary search on a sorted array? → O(log n) • What does it mean for an algorithm to run in O(1) time? → Its running time is bounded by a constant that does not depend on the input size

Correct Answer: A. O(n²)
Explanation: The inner loop runs 0 + 1 + ... + (n - 1) = n(n - 1)/2 times in total, which is still quadratic. ALSO KNOW (related points): • What is the time complexity of this code?: for (i = 0; i < n; i++); for (j = 1; j < n; j *= 2); x++; → O(n log n) • What is the auxiliary space complexity of standard (array-based) merge sort? → O(n)

Correct Answer: A. Its running time is bounded by a constant that does not depend on the input size
Explanation: A constant-time algorithm can take 1,000 steps, as long as that number does not grow with n.

Correct Answer: D. It gives an upper bound and can be used to describe the best, average, or worst case
Explanation: Big-O (upper bound), Ω (lower bound), and Θ (tight bound) describe how a function grows. Best, average, and worst cases are a separate dimension.

Correct Answer: A. An asymptotic lower bound
Explanation: A common misconception equates Ω with the best case. It is a lower bound, which can be applied to any case. ALSO KNOW (related points): • Which statement about Big-O notation is correct? → It gives an upper bound and can be used to describe the best, average, or worst case • Is the statement 'n² is in O(n³)' true? → True, because Big-O is only an upper bound

Correct Answer: B. O(n)
Explanation: Constant factors and lower-order terms are dropped.

Correct Answer: A. True, because Big-O is only an upper bound
Explanation: O(n²) is the tight bound. O(n³) is also valid, just loose.

Correct Answer: D. n!
Explanation: The order of growth is n log n < n³ < 2^n < n!. ALSO KNOW (related points): • What does O(2n + 5) simplify to? → O(n)