BPSC TRE Data Structures & Algorithms – Full Subject Test 2

Strassen's algorithm reduces matrix multiplication recursive subproblems from 8 to 7, yielding T(N) = 7T(N/2) + O($N^2)$, which evaluates to O($N^{log2$ 7}) $\approx O(N^2.807)$.

The recurrence has $a = 2$, $b = 2$ and f(n)=n. Since $n^{log_b$ a}=n, it is Master Theorem Case 2 and T(n)=Θ(n log n). Thus all three statements are correct.

Here $a = 2$, $b = 2$, f(n) = n. Since $n^{log_b$ a} = $n^1$ = $n = f(n)$, this falls into Case 2 of Master Theorem, giving T(n) = Θ(n log n).

An Upper Triangular Matrix has non-zero entries only on and above the main diagonal (total N(N+1)/2 entries). Storing only these in a 1D array reduces space from $N^2$ to N(N+1)/2.

An upper-triangular matrix has N(N+1)/2 entries on and above the main diagonal, so compact 1D storage can reduce space while preserving access through an index-mapping formula. All three statements are correct.