৪৯তম বিসিএস ⎯ কম্পিউটার সায়েন্স (CSE) [৯৭১]

Answer: C

Asymptotic notations are mathematical tools used to describe the running time or space requirement of an algorithm as the input size (n) grows very large (n → ∞).

They focus only on growth rate, i.e., how fast the runtime increases as input size increases.

Asymptotic analysis studies growth as input size approaches infinity.

Answer: B
Asymptotic analysis does not calculate exact runtime, only growth trends.

Other options are valid uses.

Answer: D

Big-O provides an asymptotic upper bound (worst-case growth).

Eg: f(n) = 3n² + 5n + 2 → O(n²).

Answer: A

O(1) = constant → independent of input size.
Example: accessing an array element.

Answer: C
Growth hierarchy: 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
O(1) → Flat line
log n → Slow rise
n → Straight line
n log n → Slightly faster than linear
n² → Steep curve
2ⁿ → Explodes rapidly
n! → Even faster than exponential

 Answer: B
Explanation: n² grows faster than √n and log variations.

Answer: D
Explanation: Big-Θ provides tight bounds (both upper and lower simultaneously).

(Big-O): Upper bound (worst case).
Ω (Big-Omega): Lower bound (best case).
Θ (Big-Theta): Tight bound.
o (Little-o): Strictly smaller growth.
ω (Little-omega): Strictly larger growth.

Answer: B
Merge Sort divides the array into halves, sorts recursively, and merges results → classic divide and conquer

Answer: D
A Divide & Conquer (D&C) algorithm does three things:

Divide: Split the problem of size n into smaller subproblems (often 2 halves).
Conquer: Solve each subproblem recursively.
Combine: Merge the sub-results into the full answer.
Merge sort, Binary search and Quick sort algorithm are based on Divide & Conquer

 Bubble sort is iterative (comparison-based), not divide-and-conquer.

Answer: A
Explanation: Divide and Conquer   → Divide → Solve (recursively) → Combine.

Answer: C
Explanation: If pivot is smallest/largest → highly unbalanced recursion → O(n²).

Best Case / Average Case: Pivot divides the array almost equally each time.
Example: size n = 16, pivot splits into 8 + 7.

Recurrence: T(n) = 2T(n/2) + Θ(n)  
                          ⇒ Θ(n log n)

Depth of recursion = log n, each level costs Θ(n).
        Total = Θ(n log n).

Worst Case (Pivot = smallest/largest element)

Suppose pivot is always the smallest element:

Left side = 0 elements, Right side = n−1 elements.

Example: Sorting [1, 2, 3, 4, 5] with pivot = smallest.

Recurrence becomes: T(n) = T(n−1) + Θ(n)

Partitioning costs Θ(n). Then we recurse on n−1 elements.

T(n) = T(n−1) + n  
     = T(n−2) + (n−1) + n  
     = …  
     = Θ(1 + 2 + 3 + … + n)  
     = Θ(n²)

Answer: C
Merge sort always divides and merges in O(n log n), regardless of input.

Quick Sort : average Θ(n log n) but worst-case Θ(n²) (pivot-dependent).

Selection Sort: always Θ(n²) — no divide step.

Insertion Sort : worst Θ(n²), best O(n) (nearly sorted arrays).

So Merge Sort is the only one of the four that always runs in Θ(n log n).

Answer: D Quick Sort is faster in practice for large database

Average time complexity: Θ(n log n), same as Merge Sort and Heap Sort.

Cache-friendly: Works mostly in-place (good memory locality).

Low constant factors: Less overhead compared to Merge Sort’s extra arrays and Heap Sort’s swaps.
On the other hand
Merge Sort: Guarantees O(n log n), but needs extra space (O(n)) and has more overhead.

Heap Sort: O(n log n) worst-case, but more comparisons and less cache-efficient → slower in practice.

Bubble Sort: Always O(n²), far too slow for large datasets.

Answer: B
Dynamic Programming (DP) is effective when the problem has overlapping subproblems (same subproblem appears multiple times) and optimal substructure (solution can be composed from sub-solutions).

 Answer: D
Fibonacci Numbers is an example of a Dynamic Programming. Fibonacci computation has overlapping subproblems. Memorization or tabulation avoids redundant computations.
Where, Binary search, Quick sort, Merge sort are the example Divide and Conquer approach.

Answer: D
Explanation: All these problems have optimal substructure and overlapping subproblems, suitable for DP.

Answer: B
DP is about solving overlapping subproblems once, storing results (memoization or tabulation), and reusing them to avoid recomputation. This reduces exponential problems (like Fibonacci recursion) to polynomial.

Answer: C
 Greedy-choice is used in greedy algorithms, not DP.

Answer: B) 0/1 Knapsack Problem
Explanation: 0/1 Knapsack (decision) is NP-Complete (in NP), not NP-Hard whereas remaining three are NP- hard .

Answer: C
Explanation: Space complexity = memory needed for input, variables, recursion, etc.

Answer: B) Hard to solve, easy to verify

P: Easy to solve, easy to verify.
NP-Complete: The hardest problems in NP but easy to verify (both NP + NP-Hard).
NP-Hard: Harder than NP, not always verifiable in polynomial time.

Answer - B) The approach followed in Floyd Warshall’s algorithm is dynamic programming.

 Answer: B
Explanation: Greedy algorithms repeatedly make a local optimal choice (a greedy choice) and never reconsider it. They work when local choices lead to a global optimum (via greedy-choice property + optimal substructure).
Option
A is divide & conquer;
C is brute-force;
D is backtracking.

 Answer: C
Explanation: Both Kruskal (pick smallest-weight edges that don’t form a cycle) and Prim (grow a tree by adding smallest-weight edge crossing the cut) are greedy. Correctness proofs use cut and cycle properties (exchange arguments). Typical complexities: Kruskal O(E log E), Prim with heap O(E log V).

Answer - A) Time and space complexity are the main measures of the efficiency of an algorithm.

Answer: C
Explanation: 0/1 Knapsack requires Dynamic Programming because greedy may fail; fractional Knapsack is solvable greedily.

Answer: B
Explanation: Huffman coding combine two nodes with smallest frequency iteratively → ensures minimal total cost.
example:
| Symbol | Frequency |
| ------ | --------- |
| A      | 5             |
| B      | 9             |
| C      | 12          |
| D      | 13         |
| E      | 16         |
| F      | 45         |

Pick 5 (A) and 9 (B) → combine to 14
Pick 12 (C) and 13 (D) → combine to 25
Pick 14 and 16 (E) → combine to 30
Pick 25 and 30 → combine to 55
Pick 45 (F) and 55 → root = 100
Resulting Huffman tree minimizes total weighted path length.

Answer: B
Explanation: Branch and Bound (B&B) is designed for combinatorial optimization problems, like Travelling Salesman, Knapsack, etc.

Answer: D
Explanation: B&B is flexible. DFS uses less memory, BFS explores level by level, and best-first explores nodes with the best bound first (often faster).

Answer: A
Explanation: B&B reduces search but may still explore many nodes if the bound is weak (not tight) or the branching factor is large. Proper bound calculation is crucial for efficiency.

Answer: B
Explanation: Jarvis March constructs convex hull by wrapping points → O(nh), h = number of hull points

Answer: C
Explanation: Sweep line technique is widely used in line intersection, closest pair, and other geometric problems.

 Answer: B
Explanation: A graph ?= (?, ?) consists of vertices (nodes) and edges connecting pairs of vertices. Trees are a special type of graph.

 Answer: A
Explanation: In a connected undirected graph, there is a path between every pair of vertices.

Answer: A
BFS explores all vertices at the current level before moving to the next level.

Answer: B
Explanation: BFS is level-order, DFS goes deep along a path first.

Answer: B
Explanation: DFS maintains recursion stack; a back edge indicates a cycle.

Answer: C
Explanation: A spanning tree connects all vertices without cycles → exactly V-1 edges.

Answer: B
•    Kruskal = greedy algorithm → pick lightest edge → avoid cycles → build MST (Minimum Spanning Tree)

Answer: B
Explanation: Prim with adjacency matrix → O(V^2), efficient for dense graphs. Kruskal better for sparse graphs

Answer: C
Explanation: Number of spanning trees depends on graph connectivity and edges; multiple MSTs possible if weights allow.

Answer: C
Explanation: MST
Connects all vertices with V-1 edges (spanning), 
Has minimum possible total edge weight
Forms a tree (no cycles)

Answer: A
Explanation: Bellman-Ford handles negative weights, but not negative cycles for shortest path

Answer: B

 Max-Flow computes the largest possible flow from a source vertex to a sink vertex, respecting edge capacities.

Answer: D
Applications of Max-Flow problem include network design, traffic flow, bandwidth, matching problems, and resource allocation (scheduling)

Output: C ) n(n-1)/2
Explanation: First for loop will run for (n) times and another for loop will be run for (n-1) times as the inner loop will only run till the range i which is 1 less than n, 
so overall time will be n(n-1)/2.

 Answer: B
Pseudocode is a simplified representation of a program's logic, written in plain English to make it easy to understand. Pseudocode helps design logic without worrying about syntax.

 Answer: A
Complexity is measured as a function of input size (n).