Time/Space Tradeoffs - C Plus Plus

1. If the program needs only the final sequence value, which modification best improves the time/space tradeoff without increasing asymptotic running time?
   Answer: Use a bottom-up loop retaining only the two preceding values, giving $O(n)$ time and $O(1)$ additional space. When a sequence depends only on its two most recent values — like the Fibonacci sequence — you should immediately ask yourself: do I actually need to store all previous values, or just enough to compute the next one? This question tests whether you can identify unnecessary memory usage and eliminate it without harming time complexity. A bottom-up iterative approach answers this perfectly. Instead of recursing or caching an array of $n$ values, you use two variables that "slide forward" through the sequence: compute the next value from the two current ones, then update. This gives you $O(n)$ time (you still perform $n$ steps) and $O(1)$ additional space (only two variables, regardless of $n$). That's why A is the best modification — it preserves the asymptotic time bound while dramatically reducing memory usage. B is wrong because it claims every cached value must be in memory simultaneously to maintain $O(n)$ time. That's false — each new value only depends on the two preceding values, not the entire history. You never need the full cache at once. C is tempting because it mentions $O(1)$ space, but removing memoization while keeping the naive recursion restores the exponential time complexity (think: redundant recomputation of overlapping subproblems). The claim of $O(n)$ running time in C is simply incorrect. D is wrong because a linked list still stores all $n$ values. Changing the data structure from a vector to a linked list doesn't change the amount of data stored — it remains $O(n)$ space, not $O(1)$. As a study tip: whenever a recurrence depends on only a fixed number of prior values (like 2), a rolling-variable loop achieves $O(1)$ space without sacrificing $O(n)$ time — always prefer it when only the final result is needed.
2. If the program needs the final cost now but might later need the exact optimal path, which statement is most accurate?
   Answer: Rolling rows preserve $O(nm)$ time and reduce space to $O(m)$, but the discarded states are generally unavailable for direct path reconstruction. When you see a dynamic-programming question involving space optimization, focus on the tradeoff triangle: time complexity, space complexity, and reconstructability. These three properties cannot always be optimized simultaneously. The rolling-rows technique works by keeping only the current and previous rows in memory at any time. Since the recurrence only looks one row back, this is sufficient to compute the final optimal cost correctly — so the $O(nm)$ time is fully preserved while space drops from $O(nm)$ to $O(m)$. The catch is that once you overwrite a row, those intermediate states are gone. If you later need to reconstruct the optimal path — which requires tracing predecessor decisions back through every cell — you no longer have that data. That's exactly what C captures: rolling rows preserve time and reduce space, but sacrifice the ability to reconstruct the path directly. A is wrong because keeping the full table doesn't change the time complexity at all — you still must compute every cell, so time remains $O(nm)$, not $O(n+m)$. This distractor conflates "data being available" with "less work being done." B is wrong because it claims rolling rows "always allow direct path reconstruction." This is the opposite of the truth — rolling rows specifically discard the predecessor states needed for reconstruction. D is wrong because rolling rows do not affect the cost computation's time complexity. The recurrence structure is unchanged; you simply reuse two row-sized buffers. Time stays $O(nm)$. A useful mental rule: space optimization via rolling arrays trades reconstructability for memory. On exam questions, whenever you see both space reduction and path reconstruction mentioned together, immediately ask yourself which one is being sacrificed.
3. Which comparison most accurately describes the time/space tradeoff between iterative deepening and breadth-first search?
   Answer: Iterative deepening uses about $O(d)$ path space and $O(b^d)$ time, trading repeated expansions for much lower memory than breadth-first search. When comparing search algorithms, always think about two separate resources: time (how many nodes get expanded) and space (how many nodes must be stored simultaneously). These can trade off dramatically depending on the algorithm's structure. Iterative deepening depth-first search (IDDFS) works by running depth-limited DFS repeatedly — first to depth 0, then 1, then 2, up to depth $d$. Because it uses DFS internally, it only needs to store the current path from root to the frontier node, giving it $O(d)$ space. The cost is re-expanding nodes multiple times: nodes near the root get visited in every iteration. However, since most nodes live near depth $d$ in a tree with branching factor $b$, this overhead is a small constant multiplier — total time is still $O(b^d)$. This makes A correct: IDDFS trades repeated expansions for dramatically reduced memory compared to BFS. B has the complexities backwards. IDDFS does not achieve $O(d)$ time — it revisits nodes across iterations. And its space is $O(d)$, not $O(b^d)$. C describes the wrong algorithm. It is IDDFS (or plain DFS) that stores only the current root-to-node path in $O(d)$ space — BFS must store the entire frontier, which grows to $O(b^d)$ at depth $d$. D is false because the whole point of IDDFS is to avoid $O(b^d)$ space while still guaranteeing optimality on unweighted trees. As a study tip: remember the mantra — "Iterative deepening: DFS memory, BFS optimality." It gives you the best of both worlds on time complexity, but the memory savings are the key motivation.
4. As $M$ grows, which choice gives the better asymptotic time/space tradeoff for this workload?
   Answer: Compute answers directly because total time is $\Theta((\log M)^2)$ and additional space remains $\Theta(1)$. When analyzing time/space tradeoffs, you need to account for all costs: preprocessing, query time multiplied by query count, and space. Don't assume one phase dominates without doing the math. Here, the number of queries is $Q = \lceil \log_2 M \rceil$. For the direct computation approach, total time is $\Theta(\log M) \times \Theta(\log M) = \Theta((\log M)^2)$, and space stays $\Theta(1)$ since no table is stored. This is exactly what B describes — making it correct. For the table approach, you pay $\Theta(M)$ upfront in both time and space, then $\Theta(1)$ per query. Total time becomes $\Theta(M) + \Theta(\log M) \cdot \Theta(1) = \Theta(M)$, and space is $\Theta(M)$. Since $M$ grows much faster than $(\log M)^2$, direct computation wins on both dimensions. A is wrong because it blindly assumes constant-time queries always justify preprocessing — they do when query count is large (e.g., $\Theta(M)$ queries), but with only $\Theta(\log M)$ queries, the $\Theta(M)$ setup cost is never recovered. C incorrectly claims the table's total time is $\Theta(\log M)$, ignoring the dominant $\Theta(M)$ preprocessing term entirely. D is a vague handwave — "fewer than $M$ queries" doesn't make the methods equivalent; you must compare actual asymptotic expressions. As a strategy, always compute total cost = preprocessing + (queries × per-query cost), then compare methods side by side. A cheap per-query cost is only worth paying for if the fixed setup cost is proportionally justified by query volume.
5. Which statement correctly compares the worst-case total costs of the two approaches?
   Answer: Direct scanning uses less space but may take $O(n^4)$ total time; prefix sums use $O(n^2)$ extra space and $O(n^2)$ total time. When comparing algorithmic approaches, always analyze both time and space across the full workload — not just a single operation. Here, you have $n^2$ queries on an $n$-by-$n$ grid. With direct scanning, each query costs up to $O(n^2)$, so $n^2$ queries cost $O(n^2) \times O(n^2) = O(n^4)$ total. It uses no extra space beyond the grid itself. With prefix sums, you pay $O(n^2)$ once to build the auxiliary array, then each of the $n^2$ queries costs $O(1)$, giving $O(n^2) + O(n^2 \cdot 1) = O(n^2)$ total time, with $O(n^2)$ extra space for the prefix array. That's exactly what D describes — making it the correct answer. A is wrong because prefix-sum preprocessing is $O(n^2)$, not $O(n^4)$. You only scan each cell once to build cumulative sums; you don't precompute every possible rectangle result. B is wrong because direct scanning is emphatically not $O(n^2)$ total — it's $O(n^4)$. The two approaches have dramatically different total time costs, not equal ones. C is wrong on the space claim. While it's true each individual query reads only four values from the prefix array, the array itself still occupies $O(n^2)$ space. Reading few entries at query time doesn't eliminate the memory used to build the structure. As a study tip: when evaluating preprocessing trade-offs, always multiply per-query cost by the number of queries and add it to setup cost. This "total cost" framing is what makes prefix sums shine over brute force at scale.
6. Which method provides the best valid time/space tradeoff under this constraint?
   Answer: Heap sort, taking $O(n \log n)$ worst-case time while using $O(1)$ additional memory. When a question pairs a time complexity goal with a strict memory constraint, you need to evaluate both dimensions simultaneously — an algorithm that wins on time but violates the space rule is simply off the table. Here, the constraint is $O(1)$ additional memory. That single requirement eliminates two of the four options immediately. Option A, counting sort, requires allocating a counting array of size $n^2$, which is $O(n^2)$ extra memory — a direct violation. Option C, merge sort with a temporary array, needs $O(n)$ extra memory for the scratch space used during merging — also a violation, even though $O(n)$ sounds modest. That leaves B and D, both of which satisfy the $O(1)$ space constraint. The difference comes down to time. Insertion sort (B) has a worst-case time complexity of $O(n^2)$ — this occurs when the input is reverse-sorted, and no clever input arrangement can avoid it. Heap sort (D), by contrast, guarantees $O(n \log n)$ in the worst case, not just on average. It builds a max-heap in-place and repeatedly extracts the maximum, never requiring more than a constant amount of extra storage. Since $O(n \log n)$ is strictly better than $O(n^2)$ for large $n$, heap sort is the clear winner. Notice that the values ranging up to $n^2 - 1$ is a deliberate distractor — it makes counting sort look tempting, but the memory cost makes it invalid here. Study tip: On sorting questions with constraints, always check memory first to eliminate options, then compare time complexities among what remains.
7. Which representation satisfies the memory requirement and provides the strongest valid worst-case edge-test bound among the choices?
   Answer: Sorted adjacency lists, using $O(V+E)$ memory and providing $O(\log \deg(u))$ worst-case edge tests. When choosing a graph representation, you need to evaluate two constraints simultaneously: memory usage and worst-case (not average-case) edge-test complexity. These constraints can conflict, so always check both before selecting an answer. Sorted adjacency lists satisfy the $O(V+E)$ memory requirement because you store exactly the edges that exist — with $E = \Theta(V)$, this is $O(V)$ total. For edge tests, binary search over a sorted neighbor list runs in $O(\log \deg(u))$ worst case, which is a provable, unconditional guarantee. This makes B the correct answer: it meets memory requirements and provides the strongest valid worst-case bound among the choices. Here's why the other options fall short. A uses an adjacency matrix, which costs $O(V^2)$ memory — fine for dense graphs, but this violates the $O(V+E) = O(V)$ memory constraint entirely. The $O(1)$ edge test doesn't help if you can't afford the structure. C claims $O(1)$ worst-case edge tests for unsorted lists "because the graph is sparse" — this is a classic trap. Sparsity reduces average list length but does not change the worst case; you could still have one vertex with $O(V)$ neighbors, making worst-case traversal $O(V)$, not $O(1)$. D sounds appealing, but hash sets only guarantee $O(1)$ expected (average) time under standard assumptions — worst-case hash set lookup is $O(n)$ due to collisions. The word "guaranteeing" makes D factually incorrect. The key study tip: always distinguish worst-case from average-case complexity. Exam questions will bait you with average-case performance presented as a worst-case guarantee — especially with hash tables and sparse structures.
8. Which statement correctly characterizes this time/space tradeoff?
   Answer: Materialization uses $O(n)$ extra space and performs $n$ transformations rather than $2n$, but both approaches still take $\Theta(n)$ asymptotic time. Whenever you see a question about time/space tradeoffs involving repeated computation, your job is to carefully count operations and memory usage at the asymptotic level — not just the intuitive level. Here, materializing the $n$ transformed values requires $O(n)$ extra space to store them. In exchange, you perform each transformation exactly once: $n$ total transformations for two passes instead of $2n$. However, both $n$ and $2n$ are $\Theta(n)$ — a constant factor difference doesn't change asymptotic class. So materialization trades space for a constant-factor reduction in work, not an asymptotic improvement. That makes A correct. B is the most tempting distractor. It correctly identifies the $O(n)$ space cost, but falsely claims materialization improves asymptotic time from $\Theta(n^2)$ to $\Theta(n)$. Lazy recomputation still only visits each of the $n$ elements twice — that's $2n$ work, which is $\Theta(n)$, not $\Theta(n^2)$. An $n^2$ blowup would require something like nested passes, which isn't the scenario here. C is doubly wrong. Lazy recomputation does use $O(1)$ extra space (no storage of transformed values), but claiming $\Theta(\log n)$ time makes no sense — fetching and transforming each element on demand across two passes is still $\Theta(n)$ work, not logarithmic. D incorrectly claims both strategies use the same asymptotic space. Lazy recomputation never stores all transformed values simultaneously, so it uses $O(1)$ extra space versus $O(n)$ for materialization — a real asymptotic difference. Study tip: Always distinguish between asymptotic improvements (changing the complexity class) and constant-factor improvements (same class, smaller coefficient). Exam questions frequently conflate the two to test whether you truly understand Big-O notation.
9. Which statement best describes the guaranteed benefit and cost of caching all distinct results?
   Answer: It reduces expensive evaluations from $n$ to $\sqrt n$ while using $O(\sqrt n)$ result storage and adding logarithmic cache operations. When you see a question combining caching with asymptotic analysis, your job is to carefully track two things independently: how the cache changes the number of expensive evaluations, and what overhead the cache itself introduces. Here's the key reasoning for why C is correct. You have $n$ total requests but only $\sqrt{n}$ distinct argument values. Without caching, you'd call the expensive function $n$ times. With caching, each distinct argument triggers exactly one expensive evaluation on its first occurrence — every subsequent request for that argument is a cache hit. So expensive evaluations drop from $n$ to exactly $\sqrt{n}$. Storing one result per distinct argument requires $O(\sqrt{n})$ space. The catch: a balanced-tree cache (like a std::map) performs lookups and inserts in $O(\log(\sqrt{n})) = O(\log n)$ time, so each of the $n$ requests pays a logarithmic overhead. Answer C captures all three of these facts accurately. A is wrong on both counts — balanced-tree access is $O(\log n)$, not $O(1)$, and storage scales with the number of distinct values, not $O(1)$. B overstates the benefit: only requests after the first occurrence of each value become cache hits. The first occurrence of each of the $\sqrt{n}$ distinct values still requires a full evaluation, so you can't reduce evaluations to $O(1)$. D presents a false general claim — caching is beneficial precisely when cache lookup is cheaper than re-evaluation, which is the whole motivation for memoization. When analyzing caching problems, always separate the reduction in expensive work from the overhead of cache operations — exam questions frequently test whether you account for both.
10. Which strategy gives the lowest worst-case total running time while satisfying the additional-memory limit?
    Answer: Sort the vector in place, then use binary search, using $O(\log n)$ additional memory and $O(n \log n)$ total time. When a question constrains additional memory while asking you to minimize worst-case time, you need to evaluate each option along both dimensions simultaneously — not just pick the fastest algorithm in isolation. Sorting the vector in place (using something like std::sort, which runs in $O(n \log n)$ and requires only $O(\log n)$ stack space for recursion) lets you then answer each of the $n$ queries with binary search in $O(\log n)$ each. Total time: $O(n \log n)$ for sorting plus $O(n \log n)$ for all queries — still $O(n \log n)$ overall. This is option B, and it satisfies the $O(\log n)$ memory constraint perfectly. Option A is the naïve approach: scanning the full vector for every query costs $O(n)$ per query, giving $O(n^2)$ total — far worse, even though the memory is minimal. Option C is tempting because $O(n)$ expected total lookup time sounds ideal, but building an std::unordered_set requires $O(n)$ additional memory to store all $n$ elements — this violates the constraint. Also note "expected" time isn't worst-case. Option D sorts a copy of the vector, which also requires $O(n)$ additional memory for the copy itself — another constraint violation, even though the time complexity matches B. The key study tip: constraints eliminate options before you optimize. On algorithmic questions, always filter by every stated constraint first (here, $O(\log n)$ memory), then choose the fastest survivor. This two-pass thinking prevents you from being seduced by asymptotically faster algorithms that break the rules.

Start this quiz