Mixed array review

Questions 1 to 5 of 6

1. 1. The simple way adds up every window from scratch. What is the time complexity of the fixed-size sliding window, which keeps a running sum, for n values and any window size k?

   O(n * k)O(k)O(n)O(n squared)
2. 2. A difference array holds n values plus one extra entry. How much work does one range update take, where it adds v to every value from index l to index r?

   O(n), because it walks the whole arrayO(1), because it makes two writes to the difference arrayO(k), one step for each value in the rangeO(n log n), because the updates are sorted first
3. 3. Predict the output of this program. Ignore the trailing space after the last value. ``cpp #include <iostream> #include <vector> using namespace std; int main() { vector<int> diff(7, 0); diff[1] += 3; diff[4] -= 3; diff[0] += 1; diff[2] -= 1; int run = 0; for (int i = 0; i < 6; i++) { run += diff[i]; cout << run << ' '; } cout << '\n'; } ``

   1 3 2 2 0 00 3 2 2 0 01 4 3 3 -3 01 4 3 3 0 0
4. 4. Why does rotateRight call k %= n before it reverses anything?

   It sorts the array before rotating, so the reversals are correctIt stops the function early for an empty array, so the reversals are skippedA rotation by k larger than n repeats, so k % n gives the same result with fewer stepsIt converts k from int to size_t, so the reversal can use it
5. 5. In a jagged array, a loop over row r reads each value in that row. Which inner loop bound is safe?

   jagged[r].size(), the length of the row being readjagged.size(), the number of rowsjagged[0].size(), the length of the first row3, the length of the longest row in the example