Application lab in ADT Contracts and Complexity

Mission

Compare an explicit cost model for an array list and a singly linked list, then report the cheaper choice or a tie.

Learning outcome: Select a structure from workload evidence

Correctness contract

Invariant: An ADT contract describes observable behavior independently from implementation.

Required technique: Evaluate both supplied workload formulas with long arithmetic and compare their totals; do not use a size threshold or an unexplained heuristic.

Complexity target: time O(1); space O(1).

Input and output

Input: Three integers: item count n, number of indexed reads, and number of front insertions. Whitespace may be spaces or line breaks.

Output: Print array-list, linked-list, or tie. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• 1 <= n <= 1,000,000.
• Read and insertion counts are non-negative and every modeled total fits in signed 64-bit storage.
• Array-list cost = indexedReads + frontInsertions*n; linked-list cost = indexedReads*n + frontInsertions.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Evaluate both supplied workload formulas with long arithmetic and compare their totals; do not use a size threshold or an unexplained heuristic.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

100 1000 2

Sample output

array-list

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Evaluate arrayCost = reads + inserts*n and linkedCost = reads*n + inserts, then compare the two totals. Input `100 1000 2` therefore produces `array-list`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.