What is the average-case time complexity of searching for a specific value in an unsorted 1D array of size n?
In an unsorted array, a value may require scanning a linear number of elements. The average-case search time is Θ(n), while direct access by a known index is O(1).
What does a band matrix with bandwidth k represent?
A band matrix has non-zero entries only within a specified range k of the main diagonal, zeroing out elements outside this band.
How many elements are stored when an N $\times N tridiagonal matrix$ is represented compactly in a 1D array?
A tridiagonal matrix has N elements on the main diagonal, N-1 on the sub-diagonal, and N-1 on the super-diagonal, for a total of 3N-2 stored elements.
Which problem complexity class contains decision problems that can be solved in polynomial time by a deterministic Turing machine?
Class P consists of all decision problems solvable in polynomial time O($n^k)$ by a deterministic computer algorithm.
What is the worst-case space complexity of a recursive algorithm with maximum call stack depth D?
Each active function call pushes a stack frame onto the call stack. A maximum call depth of D consumes O(D) auxiliary stack space.