What is the time complexity of searching for an element in an unsorted 1D array of size N?
Searching an unsorted array requires scanning elements sequentially from index 0 to N-1 in worst case, taking O(N) time.
Ignoring per-entry byte-size differences and measuring storage in scalar entries, approximately what percentage of storage is saved when converting a dense 1000x1000 matrix with 1% non-zero entries to COO triplet representation?
The dense representation stores 1,000,000 matrix entries. With 1% non-zero entries there are 10,000 non-zero values; COO stores three scalar fields per non-zero entry, or about 30,000 scalar entries. On this entry-count basis, the saving is (1,000,000 - 30,000)/1,000,000 = 97%.
What is the recursion time complexity of the Karatsuba fast integer multiplication algorithm?
Karatsuba algorithm reduces 4 half-size multiplications to 3, giving T(N) = 3T(N/2) + O(N), which evaluates to O($N^{log2$ 3}) $\approx O(N^1.585)$.
In a lower triangular matrix of size N x N, how many elements below and including the main diagonal are stored?
Row 1 has 1 element, Row 2 has 2... Row N has N elements. Total = 1 + 2 + ... + $N = N(N+1)/2 elements$.
For T(n) = T(n-1) + n with T(1)=1, which asymptotic solution is correct?
The recurrence expands to 1 + 2 + ... + n = Θ($n^2)$. Since Θ($n^2)$ is not among A-C, the correct choice is E: None of the above.