Algorithm Analysis: Master the Art of Algorithm Efficiency

Question 1

Which of the following is a valid asymptotic bound for the function f(n) = n^3 + 2n^2 + 5n + 1?

Accepted Answer

O(n^3)

Answer

O(n^2)

Answer

O(n log n)

Answer

O(1)

Question 2

The space complexity of an algorithm refers to:

Accepted Answer

The maximum amount of memory required by the algorithm during its execution

Answer

The amount of memory required to store the input

Answer

The amount of memory required to store the output

Answer

The number of steps required to execute the algorithm

Question 3

Which of the following sorting algorithms has a worst-case time complexity of O(n^2)?

Accepted Answer

Bubble Sort

Answer

Merge Sort

Answer

Quick Sort

Answer

Heap Sort

Question 4

An algorithm that performs a constant number of operations regardless of the input size has a time complexity of:

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 5

Which of the following actions **cannot** improve an algorithm's efficiency?

Accepted Answer

Enlarging the input data set

Answer

Decreasing the number of operations performed

Answer

Optimizing the algorithm's code

Answer

Choosing a more suitable data structure

Question 6

Determine the time complexity of a loop that executes 1000 iterations.

Accepted Answer

O(1000)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 7

Which of the following is NOT a valid asymptotic notation?

Accepted Answer

∃(n)

Answer

O(n)

Answer

Ω(n)

Answer

Θ(n)

Question 8

An algorithm has a time complexity of O(n^2). What does this indicate?

Accepted Answer

The algorithm's running time increases quadratically with input size.

Answer

The algorithm's running time increases linearly with input size.

Answer

The algorithm's running time increases exponentially with input size.

Answer

The algorithm's running time is constant regardless of input size.

Question 9

Which of the following sorting algorithms has a worst-case time complexity of O(n^2)?

Accepted Answer

Bubble Sort

Answer

Merge Sort

Answer

Quick Sort

Answer

Heap Sort

Question 10

True or False: Amortized analysis is a technique used to analyze the average time complexity of an algorithm over a sequence of operations.

Accepted Answer

True

Answer

False

Question 11

For a linear search algorithm applied to an array of size 'n', what is its time complexity?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Question 12

Which of the following is a key limitation of asymptotic analysis?

Accepted Answer

It does not provide exact execution times for specific inputs

Answer

It only works for algorithms with constant time complexity

Answer

It cannot handle all possible input types

Answer

It is too complex to use in practice

Question 13

When analyzing the space complexity of a binary search tree, what is its complexity?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 14

Which sorting algorithm has a time complexity of O(n^2) in the worst case?

Accepted Answer

Bubble sort

Answer

Merge sort

Answer

Quick sort

Answer

Heap sort

Question 15

What is the concept of 'amortized analysis' in algorithm analysis?

Accepted Answer

Analyzing the average performance of an algorithm over multiple operations

Answer

Analyzing the worst-case performance of an algorithm under specific scenarios

Answer

Analyzing the best-case performance of an algorithm

Answer

Analyzing the performance of an algorithm on a predetermined input set

Question 16

What is the time complexity of a lookup operation in a hash table?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 17

Determine the order of growth for the function f(n) = n^2 + 3n + 5:

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(2^n)

Question 18

Which algorithm exhibits a best-case time complexity of O(1)?

Accepted Answer

Binary search

Answer

Linear search

Answer

Merge sort

Answer

Quick sort

Question 19

Calculate the space complexity of the following code snippet:
            
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
              arr[i] = i;
            }

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Question 20

Which asymptotic notation represents the weakest growth rate?

Accepted Answer

O(n)

Answer

O(n log n)

Answer

O(n^2)

Answer

O(2^n)

Question 21

Which of the following properties is NOT inherent to asymptotic complexity analysis?

Accepted Answer

Provision of precise running times

Answer

Comparison of algorithm efficiencies

Answer

Simplification of analysis for intricate algorithms

Answer

Identification of dominant operations

Question 22

What is the Big-O notation for an algorithm with a time complexity of O(n^2)?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(2^n)

Question 23

Which sorting algorithm exhibits a worst-case time complexity of O(n^2)?

Accepted Answer

Bubble Sort

Answer

Merge Sort

Answer

Quick Sort

Answer

Heap Sort

Question 24

What is the space complexity of an algorithm that utilizes a linked list to store n elements?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(2^n)

Question 25

Which asymptotic notation represents the fastest growth rate?

Accepted Answer

O(2^n)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 26

What is the time complexity of performing a binary search on a sorted array of n elements?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 27

Which concept is fundamental in the analysis of recursive algorithms?

Accepted Answer

Recurrence relation

Answer

Master theorem

Answer

Asymptotic analysis

Answer

Divide and conquer

Question 28

Calculate the time complexity of the following algorithm segment:

```
for i = 1 to n
  for j = 1 to n
    statement
```

Where n is the input size.

Accepted Answer

O(n^2)

Answer

O(1)

Answer

O(n)

Answer

O(n^3)

Question 29

Which of these is NOT a standard notation for expressing asymptotic time complexity?

Accepted Answer

O(n^2 + n)

Answer

O(n)

Answer

Θ(n)

Answer

Ω(n)

Question 30

What is the time complexity of a binary search algorithm?

Accepted Answer

O(log n)

Answer

O(n^2)

Answer

O(n)

Answer

O(1)

Question 31

In algorithm analysis, 'big-O' notation describes:

Accepted Answer

An upper bound on the worst-case time complexity

Answer

The space complexity of the algorithm

Answer

A lower bound on the best-case time complexity

Answer

The exact average-case time complexity

Question 32

Which sorting algorithm below has a time complexity of O(n^2) in the best case?

Accepted Answer

Insertion Sort

Answer

Quick Sort

Answer

Heap Sort

Answer

Merge Sort

Question 33

What is the space complexity of a recursive algorithm that makes 'n' recursive calls?

Accepted Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Answer

O(1)

Question 34

What is the time complexity of a depth-first search (DFS) algorithm on a complete binary tree with 'n' nodes?

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(1)

Answer

O(n^2)

Question 35

Which example below demonstrates the divide-and-conquer algorithm design paradigm?

Accepted Answer

Merge Sort

Answer

Dynamic Programming Algorithm

Answer

Greedy Algorithm

Answer

Sequential Search