Java: Exam 2 Chapter 4-6

What is an array in Java?

A fixed-size, ordered collection of elements of the same type stored in contiguous memory.

How do arrays differ from ArrayLists?

Arrays are fixed-size and store primitives; ArrayLists are resizable and store objects.

What is the index of the first element in an array?

0

What happens if you access an invalid array index?

Java throws an ArrayIndexOutOfBoundsException.

How do you get the number of elements in an array?

array.length

How is a 2D array structured in Java?

As an array of arrays, often representing rows and columns.

What is the difference between a pixel grid and a Cartesian grid?

Pixel grid origin (0,0) is top-left with y increasing downward; Cartesian grid origin is bottom-left with y increasing upward.

What is a ragged array?

A 2D array where each row can have a different number of columns.

What is the role of loops with 2D arrays?

Nested loops are used to access or process each element (row and column).

What is the purpose of System.nanoTime() or System.currentTimeMillis()?

To measure actual runtime for empirical time complexity testing.

Why can using system time for algorithm analysis be unreliable?

Because it depends on system load, hardware, and environment — results may vary between runs.

What is algorithm analysis?

Studying how an algorithm’s runtime and memory usage scale as input size increases.

What is Big-O notation?

A way to express an algorithm’s asymptotic upper bound — how runtime grows with input size.

Why do we ignore constants in Big-O?

Because constants have little impact on growth rate for large n.

What is O(1)?

Constant time — operation time does not depend on input size.

What is O(n)?

Linear time — operation time grows proportionally to input size.

What is O(n²)?

Quadratic time — runtime grows with the square of input size (common with nested loops).

What is O(log n)?

Logarithmic time — typical for divide-and-conquer algorithms like binary search.

What is the runtime of binary search?

O(log n)

What is the runtime of linear search?

O(n)

Why is binary search faster than linear search?

It halves the search space with each comparison.

What condition must be true to use binary search?

The array must be sorted.

What does Big-Θ (Theta) represent?

A tight bound — both upper and lower growth limits.

What does Big-Ω (Omega) represent?

An asymptotic lower bound — best-case performance.

What are the basic steps of binary search?

Check the middle element, compare, and recurse or iterate into the left or right half.

What does “time complexity” measure?

The number of basic operations an algorithm performs relative to input size n.

What does “space complexity” measure?

The amount of memory used by an algorithm relative to input size n.

How can we empirically test algorithm performance in Java?

Use timers (nanoTime) to compare execution durations for different inputs.

Why is empirical testing insufficient for algorithm analysis?

It depends on system performance and cannot generalize for all cases.

What is the purpose of algorithm analysis?

To evaluate and compare algorithms independent of machine or implementation.

What does the Arrays.sort() method use internally?

A dual-pivot quicksort for primitives and a stable mergesort for objects.

What is the difference between selection sort and insertion sort?

Selection sort repeatedly finds the minimum; insertion sort builds the sorted list one element at a time.

What are the time complexities of selection and insertion sort?

Both are O(n²).

What is merge sort’s time complexity?

O(n log n)

What are the advantages of merge sort?

Faster for large datasets and stable (preserves order of equal elements).

What is a list in computer science?

An ordered collection of elements that can grow or shrink dynamically.

What class implements a resizable list in Java?

ArrayList

What are the key methods of ArrayList?

add(), get(), set(), remove(), size(), clear()

What is the time complexity of accessing an element in ArrayList?

O(1)

Why are insertions and deletions slower in ArrayList?

Elements must be shifted to maintain order.

What is a linked list?

A data structure where elements (nodes) contain data and references to the next node.

What does a node in a linked list store?

An element (data) and a reference (pointer) to the next node.

What is the advantage of a linked list?

Efficient insertions and deletions (no shifting).

What is the disadvantage of a linked list?

Slower access because you must traverse nodes sequentially (O(n)).

What is the runtime of inserting or deleting from the beginning of a linked list?

O(1)

What is the runtime of accessing the nth element in a linked list?

O(n)

What interface do both ArrayList and LinkedList implement?

java.util.List

Why program to the List interface instead of a specific class?

To allow flexible substitution between different list implementations.

What are generics in Java?

A feature that allows classes, interfaces, and methods to operate on different data types while maintaining type safety.

What role do generics play in lists?

They ensure all elements in the list are of the same type and prevent runtime type errors.

What happens if you omit generics when declaring a list?

The list defaults to type Object, losing compile-time type checking.

What keyword declares a generic type in Java?

How does Java handle autoboxing in lists?

Automatically converts primitives (e.g., int) to wrapper objects (Integer).

What is the main idea behind using nodes and linked structures?

To dynamically allocate memory and efficiently manage collections that frequently change in size.

What is the difference between an array-based and node-based list?

Arrays use contiguous memory; linked lists use scattered nodes connected by references.

What are wrapper classes in Java?

Classes like Integer, Double, Boolean that let primitive values act as objects for use in collections.

What is the purpose of using generics with wrapper classes?

They allow ArrayLists to store objects corresponding to primitive values safely.

How do generics improve code reusability?

They enable writing flexible data structures that can work with any object type.

How can you iterate through an ArrayList or LinkedList?

Using a for-each loop, traditional for loop, or Iterator.

What is an Iterator?

An object that sequentially accesses elements in a collection without exposing internal structure.

What happens if you modify a list while using an Iterator?

It throws a ConcurrentModificationException.

What data structure would you use for fast random access?

ArrayList

What data structure would you use for frequent insertions or deletions?

LinkedList