Big-O for Collections - Java

What is the worst-case time complexity of the code?
Answer: $O(n)$ , because each node is visited once and iterator removal unlinks it in constant time When analyzing iterator-based loops over linked lists, the key question is: what does each operation actually cost at the data structure level? Java's LinkedList is a doubly-linked list, meaning every node holds a direct pointer to both its predecessor and successor. When you use an Iterator, the iterator tracks its current position internally — it already holds a reference to the node it just visited. Calling it.remove() uses that stored reference to unlink the node directly: just rewire two pointers. No traversal is needed. This makes each removal $O(1)$ , and since the while loop visits each of the $n$ nodes exactly once, the total complexity is $O(n)$ , making A correct. B is wrong because linked lists have no "balanced structure" to maintain — that concept belongs to trees like AVL or Red-Black trees. There is no $O(\log n)$ rebalancing step anywhere in a LinkedList operation. C describes the cost of list.remove(Object o) — the list's remove method — which does scan from the head to find the target element. But the code uses it.remove(), not list.remove(). The iterator already knows where it is, so no scan occurs. This is a critical distinction. D actually describes the correct reasoning for why list.remove(value) would be slow — it would scan from the head for each element, giving $O(n^2)$ — but the code in the question doesn't call that method, so D does not apply here. Study tip: Always distinguish iterator.remove() ( $O(1)$ , uses stored position) from collection.remove(value) ( $O(n)$ , searches from the beginning). This difference is a frequent exam trap.
What is the worst-case time complexity of the code?
Answer: $O(n^2)$ , because each removal shifts the remaining elements toward index zero When analyzing time complexity for list operations, you need to consider not just how many times the loop runs, but how much work each individual operation costs. In Java, ArrayList is backed by a dynamic array. When you call remove(0), you're removing the element at index zero — which sounds cheap, but it forces every remaining element to shift one position to the left to fill the gap. If the list has $k$ elements remaining, that removal costs $O(k)$ time. So the total cost across all iterations is: $O(n) + O(n-1) + O(n-2) + \cdots + O(1) = O\left(\frac{n(n+1)}{2}\right) = O(n^2)$ This makes D the correct answer. A is wrong because $O(\log n)$ implies a halving strategy, like binary search. The list does shrink each iteration, but that alone doesn't create logarithmic behavior — the shrinking actually reduces the shifting cost per step but doesn't eliminate the cumulative quadratic total. B is the most tempting trap. Yes, the loop runs exactly $n$ iterations, and if you only count iterations, $O(n)$ seems right. But this ignores the internal cost of each remove(0) call, which is not constant — it's $O(k)$ where $k$ is the current size. C is a misapplication of $O(n \log n)$ reasoning, which applies to efficient sorting algorithms. There's no halving of a search space here. Key tip: Whenever you see remove(0) or add(0) on an ArrayList, immediately think $O(n)$ per call — and multiply by the number of calls to get your total complexity.
What is the worst-case time complexity, and which change would improve it asymptotically?
Answer: $O(n^2)$ ; traverse the list with an iterator or enhanced for loop When analyzing time complexity in Java, always consider the underlying data structure — not just how the code looks on the surface. A LinkedList stores elements as nodes connected by pointers, meaning there is no direct index-based access. To retrieve the element at position i, Java must traverse the list from the head, one node at a time, taking $O(i)$ time per get(i) call. This makes the loop catastrophically expensive. For each of the $n$ iterations, list.get(i) takes up to $O(n)$ time, giving a total of $O(1) + O(2) + \cdots + O(n) = O(n^2)$ overall. The fix is straightforward: use an iterator or enhanced for loop (for (String s : list)), which advances a pointer sequentially without restarting from the head each time — reducing complexity to $O(n)$ . This confirms C is correct. A is wrong on two counts: the complexity is not $O(n)$ to begin with, and caching list.size() is a micro-optimization that doesn't change asymptotic behavior at all — size() on a LinkedList is already $O(1)$ . B is wrong because binary search requires random access (like an ArrayList) and a sorted structure. Applying it to a LinkedList would actually make things worse, not better, and the complexity claim of $O(n \log n)$ is fabricated here. D is wrong because $O(n^3)$ has no basis — copying a retrieved element is $O(1)$ and doesn't add another nested loop. Study tip: Whenever you see index-based get() on a LinkedList, immediately think $O(n^2)$ . Prefer iterators for sequential traversal of linked structures.
What is the overall time complexity of processing the list and all queries?
Answer: $O(n \log n)$ , because sorting and the collection of searches have that order When a question combines multiple algorithmic steps, you need to analyze each step's complexity separately and then determine which term dominates the total. Here, two operations happen: one sort, then $n$ binary searches. Collections.sort() uses a modified merge sort, running in $O(n \log n)$ . Each Collections.binarySearch() call runs in $O(\log n)$ , and since you run it $n$ times, the searches collectively cost $O(n \log n)$ . Adding both phases gives $O(n \log n) + O(n \log n) = O(n \log n)$ , making B correct. A is wrong because it misreads "performed once" as meaning cheap. Sorting is indeed called once, but "once" doesn't mean $O(n)$ — sorting $n$ elements always costs at least $O(n \log n)$ in the comparison model. Additionally, the searches are not performed just once; there are $n$ of them. C confuses binary search with linear search. An unsorted list would require $O(n)$ per query, giving $O(n^2)$ total — but after sorting, each binary search only needs $O(\log n)$ , not $O(n)$ . D isolates a single binary search's cost and ignores everything else. $O(\log n)$ describes one query; you still have the sort and $n - 1$ remaining queries to account for. As a strategy, whenever you see a multi-step algorithm, list each phase and its cost, multiply repeated operations by how many times they run, then sum and drop lower-order terms. This "phase-by-phase" breakdown prevents you from accidentally analyzing only one piece.
What is the worst-case time complexity of the code?
Answer: $O(n \log n)$ , because a linear search is repeated logarithmically many times When analyzing nested complexity, you need to evaluate how many times the outer loop runs and what each iteration costs — then multiply them together. The outer loop runs while step < n, doubling each time: 1, 2, 4, 8, … This produces $O(\log n)$ iterations. However, list.contains(target) on an ArrayList performs a full linear scan of all $n$ elements every single time it's called — it has no knowledge of prior searches. Since target is guaranteed not to be in the list, break never fires, meaning every iteration completes its full scan. The total work is therefore $O(n) \times O(\log n) = O(n \log n)$ , making C correct. A is tempting because it correctly identifies that the loop runs $O(\log n)$ times — but it ignores the cost inside the loop. Doubling the step controls iteration count, not the cost per iteration. B incorrectly treats contains as if its work accumulates only once across the entire loop. In reality, each call to contains independently scans the full list; there's no shared state between calls. D would apply if either the loop ran $O(n)$ times or contains itself were $O(n)$ called $O(n)$ times. The loop is logarithmic, not linear, so $O(n^2)$ overstates the complexity. Study tip: Whenever you see a method call inside a loop, always look up that method's time complexity separately and multiply — don't assume it's $O(1)$ just because it looks like a single line.
What is the total worst-case time complexity of both phases combined?
Answer: $O(n \log n)$ , because both insertion and lookup are logarithmic per value When analyzing time complexity for data structures, always break the problem into phases and add them together — then simplify using Big-O rules. A TreeSet in Java is backed by a red-black tree, a self-balancing binary search tree. For a balanced tree with $n$ elements, both insertion and lookup (contains) run in $O(\log n)$ per operation, because the height of the tree is bounded by $\log n$ . Since you're inserting $n$ values, the first phase costs $n \times O(\log n) = O(n \log n)$ . The second phase — calling contains once per original value — also performs $n$ lookups at $O(\log n)$ each, giving another $O(n \log n)$ . Combined: $O(n \log n) + O(n \log n) = O(n \log n)$ , making B correct. A is wrong because it ignores the logarithmic cost per operation. Saying operations "occur $n$ times" doesn't tell you how expensive each one is — $n$ operations at $O(\log n)$ each is not $O(n)$ . C is wrong because it confuses a TreeSet with a linear scan. A balanced tree doesn't search through all $n$ elements on each lookup — that $O(n)$ per call behavior describes an unsorted list, which would yield $O(n^2)$ total. The tree structure eliminates that. D is wrong because $O(\log n)$ describes the cost of a single operation, not the total cost across all $n$ calls. A useful habit: always multiply the per-operation cost by the number of operations before summing phases. Don't confuse one operation's complexity with the whole program's complexity.
Which statement best describes the time complexity of these append operations?
Answer: Some appends are $O(n)$ , but all $n$ appends together take amortized $O(n)$ When analyzing the time complexity of repeated ArrayList operations, you need to distinguish between the cost of a single operation and the total cost across all operations — this is where amortized analysis comes in. ArrayList starts with a small default capacity (10 in Java). Each add(value) is $O(1)$ when space is available. But when the array is full, Java allocates a new array roughly 1.5× larger and copies all existing elements — an $O(n)$ resize. Here's the key insight: resizes happen exponentially less often as the list grows. If you count all copy operations across all $n$ appends, the total work is approximately $10 + 15 + 22 + \ldots \approx 2n$ , forming a geometric series that sums to $O(n)$ . Dividing by $n$ operations gives an amortized $O(1)$ per append — making B the correct answer. A is wrong because not every append is worst-case $O(1)$ — resize operations genuinely cost $O(n)$ for that single call. A is confusing "amortized $O(1)$ " with "guaranteed $O(1)$ ." C is wrong because ArrayList has no $O(\log n)$ behavior anywhere in its append logic — that's more characteristic of tree-based structures like TreeMap. D is the most tempting trap: yes, some appends are $O(n)$ , but it doesn't follow that the total is $O(n^2)$ . That would require $O(n)$ -cost operations happening $O(n)$ times, but resizes occur only $O(\log n)$ times. Study tip: Whenever a question mentions repeated operations with occasional expensive steps, think amortized analysis — the total cost spread across all operations is often much better than the worst-case single-operation cost suggests.
Which pair gives the expected and pathological worst-case time complexities of the entire loop?
Answer: Expected $O(n)$ and pathological worst case $O(n^2)$ When analyzing loop complexity with hash maps, you need to think about two separate scenarios: the expected case (assuming good hash distribution) and the worst case (pathological collisions that degrade every operation). In this loop, you iterate over $n$ keys, and for each key you call containsKey and potentially put — both are hash-table operations. Under normal conditions, each of these runs in $O(1)$ expected time. Since you're doing constant work per iteration across $n$ keys, the total expected complexity is $O(n)$ . Under pathological collisions (e.g., all keys hash to the same bucket, forcing a linear scan of that bucket), each operation can degrade to $O(n)$ — meaning the single operation at step $k$ scans up to $k$ elements. Summing across all $n$ iterations gives $1 + 2 + 3 + \cdots + n = O(n^2)$ . This confirms A is correct: expected $O(n)$ , pathological worst case $O(n^2)$ . B is wrong because it claims expected $O(n \log n)$ — that's characteristic of tree-based structures like TreeMap, not HashMap. There's no logarithmic factor in hash-table expected lookups. C is wrong because it claims the worst case is also $O(n)$ , ignoring the quadratic blowup when collisions force linear probing or chaining across all $n$ operations. D is wrong on both counts — $O(\log n)$ for the whole loop would mean sub-linear work, which is impossible when you must visit all $n$ keys. A useful rule of thumb: whenever you see a loop over $n$ elements calling hash-map operations, the expected total is $O(n)$ , but worst-case degrades to $O(n^2)$ due to the multiplicative effect of per-operation linear time.
What is the worst-case time complexity of the construction and removal phases combined?
Answer: $O(n \log n)$ , because construction is $O(n)$ and $n$ removals each cost $O(\log n)$ When analyzing data structure operations, always separate the construction cost from the operational cost — they often differ in ways that surprise people. Java's PriorityQueue is backed by a binary min-heap. When you construct it from an existing collection using the collection constructor, Java uses the heapify algorithm, which runs in $O(n)$ time. This is a classic result: rather than inserting elements one by one (which would cost $O(n \log n)$ ), heapify works bottom-up and achieves linear time. Then, each poll() call removes the minimum element and restores the heap property via sift-down, costing $O(\log n)$ . Doing this $n$ times gives $O(n \log n)$ for the removal phase. Combined: $O(n) + O(n \log n) = O(n \log n)$ , making D the correct answer. A is tempting but wrong — while construction alone is $O(n)$ , it ignores the $O(n \log n)$ cost of $n$ poll operations. You can't discount the removal phase. B arrives at the right total complexity but for the wrong reason. It claims construction is $O(n \log n)$ (as if inserting one-by-one), which misrepresents how the collection constructor works. The distinction matters conceptually even if the final big-O looks similar. C describes a naive linear scan approach, which is not how a heap works. The heap's structure guarantees $O(\log n)$ removal, not $O(n)$ . As a study tip: remember that **heap construction from a collection = $O(n)$ , but heap sort (repeated removal) = $O(n \log n)$ **. These two facts together explain most PriorityQueue complexity questions.
What is the worst-case time complexity of this code?
Answer: $O(n)$ , because removing the last element requires no shifting of later elements When analyzing time complexity of loops that modify a data structure, you need to think about two things: how many iterations occur, and what each iteration costs. Here, the loop runs exactly $n$ times — once per element. The critical question is: what does each list.remove(list.size() - 1) call cost? In an ArrayList, removal works by nullifying the slot and decrementing the size counter. When you remove the last element specifically, there are no elements to the right that need to be shifted. This makes each removal $O(1)$ . Multiply that by $n$ iterations, and your total complexity is $O(n)$ , confirming that B is correct. A is wrong because there's no logarithmic behavior here. The valid index range shrinking doesn't require any binary search or divide-and-conquer logic — list.size() - 1 is a direct calculation, always $O(1)$ . C is wrong for the same reason as A. Finding the last index is not logarithmic; it's a single arithmetic operation on a stored size field. D describes what happens when you remove from the middle or front of an ArrayList — every element after the removed one must shift left, giving $O(n)$ per removal and $O(n^2)$ overall. But this code always removes from the tail, so no shifting ever occurs. Study tip: Always distinguish where you're removing from in an ArrayList. Removing from the end is $O(1)$ ; removing from anywhere else is $O(n)$ due to shifting. This distinction is a common trap on Java complexity questions.

Start this quiz