comp sci review

What is a list in Python?

An abstraction used to store a collection of items (like numbers, strings, or other objects).

What does indexing in Python start at?

Indexing starts at 0.

What does range(0, 5) return?

[0, 1, 2, 3, 4] — goes up to but does not include the end value.

What is a sequential (linear) search?

An algorithm that checks each item in a list one by one to find a target value.

What is the best-case time complexity of sequential search?

O(1) — target is the first element.

What is the worst-case time complexity of sequential search?

O(n) — target is at the end or not in the list.

What does the "find smallest" algorithm do?

Finds the smallest (or closest) value in a list compared to a target.

What is the time complexity of the find smallest algorithm?

O(n) — both best and worst case.

What is Selection Sort?

A sorting algorithm that repeatedly finds the largest/smallest in the unsorted part and swaps it to the correct position.

What is the time complexity of Selection Sort (best and worst case)?

O(n²) — same for both best and worst cases.

What is the formula for number of comparisons in Selection Sort?

n(n-1)/2 or ½n² - ½n

What is Insertion Sort?

A sorting algorithm that builds the sorted list one item at a time by inserting unsorted items into the correct position.

What is the best-case time complexity of Insertion Sort?

O(n) — when the list is already sorted.

What is the worst-case time complexity of Insertion Sort?

O(n²) — when the list is in reverse order.

When is Insertion Sort faster than Selection Sort?

When the list is already sorted or nearly sorted.

What does Big O notation represent?

The efficiency of an algorithm in terms of time or space as the input size grows.

In Big O analysis, what do the axes on the graph represent?

X-axis = number of items (n), Y-axis = number of comparisons.

Why would we use Binary Search?

Because it efficiently finds an item in a sorted list by repeatedly dividing the search interval in half, reducing the time complexity to O(log n).

What does Binary Search do?

Repeatedly checks the middle of the current section of the list.

What is the best case for Binary Search?

Best Case: O(1) (when the middle is the target)

What is the worst case for binary search?

O(log₂n)