Java: Final Exam

What is time complexity?

The amount of work an algorithm performs as input size grows, usually measured in number of steps rather than real time.

What is space complexity?

The amount of additional memory an algorithm needs as input size increases.

What does algorithm scaling mean?

How algorithm performance changes as input size grows; good scaling means performance remains practical for large inputs.

Linear search — best case

O(1): target is first element checked.

Linear search — worst case

O(n): must examine every element when the value is absent.

Binary search requirement

Array must be sorted before binary search can be used.

Binary search — best case

O(1): middle element matches target.

Binary search — worst case

O(log n): halves search space until exhausted.

Why worst-case analysis is used

Provides guaranteed performance bounds and avoids assumptions about typical inputs.

Average-case analysis difficulty

Requires specifying a probability distribution of inputs, which is usually not straightforward.

Definition of best-case performance

Situation where algorithm completes with minimal possible work.

Definition of worst-case performance

Situation where algorithm completes with maximal possible work.

System.currentTimeMillis purpose

Measures elapsed time in milliseconds; used for timing experiments but has limited precision.

How to experimentally measure performance

Run code with increasing input sizes and measure runtime to identify growth trends.

Binary search recurrence

T(n) = T(n/2) + O(1)

Difference between time and space complexity

Time is number of executed steps; space is memory required beyond input.

What is an interface?

A contract specifying methods a class must implement.

Why use interfaces for lists?

Allows switching between list implementations (ArrayList, LinkedList) without changing client code.

ArrayList underlying structure

Dynamic array that resizes as needed.

ArrayList access time

O(1) random access; O(n) insert/delete in middle.

LinkedList underlying structure

Sequence of nodes linked by references.

LinkedList access time

O(n) to access by index; O(1) insert/remove at known node.

When to use ArrayList

When frequent random access is needed.

When to use LinkedList

When frequent insertions or deletions occur at ends.

What is encapsulation?

Hiding internal data and exposing functionality through public methods.

What is a class?

A blueprint describing the fields and behaviors of an object.

What is an object?

An instance of a class containing actual data and methods.

Definition of recursion

A method solving a problem by calling itself with smaller inputs.

Two essential parts of recursion

Base case + recursive case.

What is a base case?

The condition under which recursion stops; returns a direct answer.

What is a recursive case?

The step where the method calls itself on a smaller subproblem.

Why base cases are required

To ensure the recursion eventually terminates.

Requirement for shrinking subproblems

Each recursive call must get closer to the base case.

Example: factorial recursion

n! = n * (n − 1)! with base case 0! = 1.

Call stack in recursion

Each recursive call pushes a new frame with its own parameters and locals.

Advantages of recursion

More natural expression of problems like trees, lists, divide-and-conquer.

Disadvantages of recursion

More memory use; risk of stack overflow.

Template for recursive methods

Define base case(s), define recursive case(s), combine results.

What does power(n) compute?

Computes 2ⁿ recursively.

Base case of power(n)

n == 0 → return 1.

Recursive case of power(n)

2 * power(n−1)

How power(n) shrinks input

Decreases n by 1 each call.

Small work in power(n)

Multiply recursive result by 2.

What does check(s, balance) compute?

Returns true if parentheses in s are balanced.

check base case: balance < 0

Returns false immediately.

check base case: empty string

Returns (balance == 0).

check recursive behavior

'(' → +1 balance; ')' → −1 balance; other chars → unchanged.

How check shrinks input

Uses s.substring(1) to remove first character.

Small work in check()

Examines first character and adjusts balance.

What does countOnes(n) do?

Counts the number of digit 1s in integer n.

countOnes base case

n == 0 → return 0.

countOnes recursive case

If last digit is 1 → 1 + countOnes(n/10); else → countOnes(n/10).

How countOnes shrinks input

Dividing n by 10 removes last digit each call.

Small work in countOnes

Check last digit and add 1 if equal to 1.

What does printReverse(n) output?

Prints n, n−1, …, 1.

printReverse base case

If n == 0, stop.

printReverse recursive case

Print n, then printReverse(n−1)

Small work in printReverse

Print the current value.

How isPalindrome works

Checks first and last chars; if equal, recurses on substring between them.

isPalindrome base case

String of length 0 or 1 is a palindrome.

isPalindrome recursive case

isPalindrome(s.substring(1, s.length−1))

Small work in isPalindrome

Compare first and last characters.

What does rightTriangle do?

Prints a right-aligned triangle of '*' characters.

rightTriangle base case

If level > height, stop.

rightTriangle recursive case

Print 'level' stars, then call rightTriangle(height, level+1)

Small work in rightTriangle

Print one row of '*'.

General rule for recursion design

Identify base case, identify how problem shrinks, identify how recursive result is combined with small local work.

Why recursion is useful for lists

Recursive structure of lists (head + rest) maps cleanly to recursive definitions.

Why recursion is useful for trees

Trees are inherently recursive: a tree contains subtrees.

Difference between direct and indirect recursion

Direct recursion calls itself; indirect recursion calls another method that eventually calls original.

How stack overflow occurs

Recursion depth becomes too large due to missing/incorrect base case or insufficient shrinking.

Iterative vs recursive efficiency

Iterative often uses less memory; recursive sometimes simpler and clearer.

Binary search small work

Compare mid element to target.

Binary search shrink method

Half the search range by adjusting left/right pointers.

Purpose of algorithm analysis

Predict performance growth independent of machine or language.

What does O(n) mean?

Runtime grows linearly with input size.

What does O(log n) mean?

Runtime grows slowly; each step reduces problem size multiplicatively.

Example of divide-and-conquer merge sort

Divide list in half, recursively sort halves, merge results.

Why dynamic arrays require resizing

To accommodate additional elements when capacity is reached.

Resizing cost in ArrayList

Occasionally O(n) but amortized constant time for insertions.

Why LinkedList has slow indexing

Requires walking through nodes sequentially to reach an index.

Relationship between classes and objects

Objects are instances created from class templates.

Meaning of "recursive definition"

A definition that describes something in terms of a simpler version of itself.

How recursive methods use stack frames

Each call stores its own local variables until it returns.

Why substring recursion is common in string algorithms

Strings naturally shrink by removing characters.