Trace lab in ADT Contracts and Complexity

Mission

For a named loop pattern and input size n, report the exact dominant-operation count and its Big O class.

Learning outcome: Trace dominant operations across common growth classes

Correctness contract

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

Required technique: Count the stated dominant operation from the loop schema, then map that count’s growth to the matching asymptotic class.

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

Input and output

Input: One pattern token (constant, binary, single, or pairs) followed by a positive integer n. Whitespace may be spaces or line breaks.

Output: Print operations=<count> class=<Big O class>. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• n is in the range 1 through 1,000,000.
• binary means repeatedly halve an integer while it is greater than one; pairs means n by n dominant operations.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Count the stated dominant operation from the loop schema, then map that count’s growth to the matching asymptotic class.
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

constant 64

Sample output

operations=1 class=O(1)

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Count the dominant operation from the named loop pattern first; the resulting count determines the displayed growth class. Input `constant 64` therefore produces `operations=1 class=O(1)`.

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.