What is the amortized time complexity of inserting an element into a dynamic array that doubles its capacity when full?
Although reallocating memory takes O(n) worst-case time, it occurs infrequently. Spreading this cost across n insertions yields O(1) amortized time.
Which of the following functions grow faster than $n^3$ as n approaches infinity?
Each of $2^n$, $3^n$, and n! eventually grows faster than the polynomial $n^3$. Hence more than one option is correct.
If a lower triangular matrix of size N x N is stored in a 1D array in row-major order, how many total elements are stored?
A lower triangular matrix has 1 element in row 1, 2 in row 2, ..., N in row N. Summing 1 + 2 + ... + N gives N*(N + 1) / 2.
What is the space complexity of an algorithm that uses an auxiliary 2D array of size N x N?
An auxiliary matrix of dimensions N x N contains $N^2$ elements, so the auxiliary space required is O($N^2)$.
Which asymptotic notation represents the formal mathematical definition for the lower bound of an algorithm's running time?
Big $\Omega (\Omega ) notation defines$ an asymptotic lower bound, specifying that an algorithm takes at least a constant factor of f(n) time.