Time Complexity Review

Which of the following best describes the differences between selection sort, merge sort, and insertion sort?

• Selection sort repeatedly selects the smallest element, merge sort divides and merges, and insertion sort places each element into its correct position.

• Merge sort uses recursion, selection sort uses dynamic programming, and insertion sort uses hash tables.

• Selection sort and merge sort have the same time complexity, while insertion sort is the fastest in all cases.

• Insertion sort and merge sort are cool, but selection sort is not.

Answer explanation

Selection sort finds the minimum element repeatedly

Merge sort divides and then merges sorted parts

Insertion sort places elements one at a time in the correct position

What is the average time complexity of selection sort, merge sort, and insertion sort, respectiv

• O(n²), O(n log n), O(n)

• O(n log n), O(n²), O(n²)

• O(n²), O(n log n), O(n²)

• O(n log n), O(n log n), O(n log n)

Answer explanation

Selection and Insertion sorts have an average time complexity of O(n²) due to nested loops

Merge sort is more efficient at O(n log n) due to its divide-and-conquer approach

The time complexity of bubble sort is...

Answer explanation

Bubble sort has O(n²) time complexity on average due to the need for repeated passes through the array to swap adjacent elements until fully sorted

Why does merge sort require additional space compared to selection and insertion sort?

• Merge sort requires extra space for recursive calls.

• Merge sort needs temporary arrays to merge sorted halves.

• Merge sort only sorts in-place with no extra space.

• Merge sort uses more memory due to inefficient looping.

Answer explanation

Merge sort divides the array and requires temporary storage for the sorted halves during merging, increasing its space complexity to O(n)

The time complexity of a nested for loop that iterates n times in outer-loop and 50 times in inner-loop is...

Answer explanation

A single loop iterates through each element once and does 50 calculations per element, resulting in linear time complexity, O(50*n) which is O(n)

What is the time complexity to find an element in an unsorted singly linked list?

• O(1)

• O(n)

• O(log n)

• O(n²)

Answer explanation

In an unsorted linked list, you must traverse each node until the element is found, leading to O(n) time complexity.

An algorithm that divides its input in half with each recursive call, like binary search, has a time complexity of...

Answer explanation

Dividing the problem size by 2 with each step leads to a logarithmic number of calls

The time complexity of traversing all nodes in a balanced binary tree with n nodes is

Answer explanation

Traversing each node in a binary tree requires visiting each node once, resulting in linear time complexity, O(n)

What is the time complexity of a recursive function that makes two recursive calls each time, with no additional loops?

• O(n)

• O(log n)

• O(2ⁿ)

• O(n!)

Answer explanation

Each call creates two more calls, leading to exponential growth in the number of recursive calls, resulting in O(2ⁿ) complexity.

How would a O(3^n) recursive function look like? Draw in terms on function branching out to the rest. Ex) f -> f -> f etc.

Answer explanation