Algorithm Analysis: Master Time and Space Complexity

Question 1

Consider the following algorithm: for i = 1 to n, for j = 1 to n, a[i,j] += 1. What is the time complexity of this algorithm?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(n^3)

Question 2

Which of the following asymptotic notations represents the best-case time complexity of an algorithm that performs a constant number of operations regardless of the input size?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 3

Consider the following algorithm: while (n > 1), if (n is even) then n = n / 2 else n = 3 * n + 1. What is the worst-case time complexity of this algorithm?

Accepted Answer

The worst-case time complexity cannot be determined

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 4

Which of the following is NOT a valid time complexity notation?

Accepted Answer

O(n / 2)

Answer

O(n^2)

Answer

O(n log n)

Answer

O(2^n)

Question 5

Consider the following algorithm: for i = 1 to n, for j = i to n, a[i,j] += 1. What is the space complexity of this algorithm?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n^3)

Answer

O(n^4)

Question 6

Which of the following is NOT a valid asymptotic notation?

Accepted Answer

O()

Answer

Omega(n)

Answer

Theta(n)

Answer

o(n)

Question 7

Consider the following two algorithms: Algorithm A has a time complexity of O(n^2) and Algorithm B has a time complexity of O(n log n). Which algorithm is more efficient for large input sizes?

Accepted Answer

Algorithm B

Answer

Algorithm A

Answer

Both algorithms are equally efficient

Answer

Neither algorithm is more efficient than the other

Question 8

What is the purpose of big-O notation?

Accepted Answer

To represent the worst-case time complexity of an algorithm asymptotically.

Answer

The average-case time complexity of an algorithm.

Question 9

Identify the option that is NOT an asymptotic notation.

Accepted Answer

f(n^2)

Answer

O(n)

Answer

Θ(n)

Question 10

Explain the significance of O(n^2) time complexity.

Accepted Answer

The algorithm's running time grows quadratically relative to the input size.

Answer

The running time of the algorithm grows linearly with the size of the input.

Question 11

From the provided options, select the algorithm with the optimal time complexity.

Accepted Answer

Merge sort

Answer

Bubble sort

Answer

Quick sort

Question 12

Distinguish between time and space complexity.

Accepted Answer

Time complexity measures algorithm execution time, while space complexity measures memory usage.

Answer

Time complexity measures the memory an algorithm requires, while space complexity measures the time it takes to run.

Question 13

Identify an algorithm with O(1) time complexity.

Accepted Answer

Retrieving a value from a hash table.

Answer

Sorting an array of n elements.

Question 14

Which of the following is NOT a form of time complexity analysis used in computer science?

Accepted Answer

Least upper bound analysis

Answer

Big-O notation

Answer

Big-Omega notation

Answer

Average case analysis

Question 15

What does the following time complexity notation represent: O(n^2 + log n)?

Accepted Answer

The algorithm takes n^2 operations plus log n operations in the worst case

Answer

The algorithm takes n^2 operations in the best case and log n operations in the worst case

Answer

The algorithm takes n^2 operations in the average case and log n operations in the worst case

Answer

The algorithm takes log n operations in the best case and n^2 operations in the worst case

Question 16

Which of the following is a common asymptotic analysis technique used to describe the growth rate of functions?

Accepted Answer

Order of growth

Answer

Limit of a function

Answer

Derivative of a function

Answer

Integral of a function

Question 17

What is the space complexity of an algorithm that creates an array of size n and then populates it?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Question 18

What is the tightest possible upper bound for the time complexity of an algorithm that compares each element of an array of size n with every other element?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n*log n)

Answer

O(log^2 n)

Question 19

What is the time complexity of the following algorithm, which computes the factorial of n?

Accepted Answer

O(n!)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 20

Which of the following techniques is NOT used for asymptotic analysis?

Accepted Answer

Differentiation

Answer

Limits

Answer

Equivalence transformations

Answer

Substitution into known formulas

Question 21

What is the space complexity of an algorithm that recursively generates all possible subsets of a set of size n?

Accepted Answer

O(2^n)

Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Question 22

Which algorithm has a time complexity of O(n log n)?

Accepted Answer

Merge sort

Answer

Linear search

Answer

Bubble sort

Answer

Binary search

Question 23

Which of the following is **not** a valid time complexity class?

Accepted Answer

O(2^n)

Answer

O(1)

Answer

O(log n)

Answer

O(n²)

Question 24

What is the space complexity of the following algorithm: for i in range(n): sum += i?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n²)

Answer

O(log n)

Question 25

Which sorting algorithm has a worst-case time complexity of O(n²)?

Accepted Answer

Bubble Sort

Answer

Merge Sort

Answer

Quick Sort

Answer

Heap Sort

Question 26

What does the following asymptotic notation represent: f(n) = n * log n + 2n² - 5?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n²)

Answer

O(log n)

Question 27

What is the purpose of using an auxiliary stack in a non-recursive implementation of a recursive algorithm?

Accepted Answer

To store recursive calls

Answer

To store function parameters

Answer

To store temporary values

Answer

To improve time complexity

Question 28

Which of the following is **not** a factor to consider when analyzing the efficiency of an algorithm?

Accepted Answer

Processor speed

Answer

Time complexity

Answer

Space complexity

Answer

Input size

Question 29

What is the order of growth of the following function f(n) = 2n^3 + 5n^2 + 3n + 1?

Accepted Answer

O(n^3)

Answer

O(n^2)

Answer

O(n log n)

Answer

O(1)

Question 30

Which of the following algorithms has the worst-case time complexity of O(n!)?

Accepted Answer

Traveling Salesman Problem

Answer

Merge Sort

Answer

Quick Sort

Answer

Dijkstra's Algorithm

Question 31

What is the space complexity of a linked list data structure?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Question 32

What is the recurrence relation for the Fibonacci sequence?

Accepted Answer

F(n) = F(n-1) + F(n-2)

Answer

F(n) = 2F(n-1) - F(n-2)

Answer

F(n) = F(n-1) + 2F(n-2)

Answer

F(n) = F(n-1) - F(n-2)

Question 33

Which of the following is an example of a randomized algorithm?

Accepted Answer

Quick Sort

Answer

Bubble Sort

Answer

Dijkstra's Algorithm

Answer

Binary Search

Question 34

What is the best-case time complexity of a binary search algorithm?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 35

How does the selection of an appropriate hash function impact the space complexity of an algorithm that utilizes a hash table for data management?

Accepted Answer

A well-chosen hash function can reduce the algorithm's space complexity by minimizing collisions.

Answer

The algorithm's space complexity remains constant at O(n), regardless of the hash function used.

Answer

The algorithm's space complexity is fixed at O(n^2), irrespective of the hash function chosen.

Answer

The algorithm's space complexity is unaffected by the choice of hash function.

Question 36

In the asymptotic analysis of algorithms, what does Ω(f(n)) notation signify?

Accepted Answer

Ω(f(n)) establishes a lower bound for the best-case input to an algorithm.

Answer

Ω(f(n)) sets an upper limit on an algorithm's efficiency as n approaches infinity.

Answer

Ω(f(n)) describes the average-case performance of an algorithm.

Question 37

In a search engine, which algorithm's efficiency is crucial for user satisfaction?

Accepted Answer

Searching algorithm

Answer

Sorting algorithm

Answer

Compression algorithm

Answer

Encryption algorithm

Question 38

An algorithm iterates through every element in a list of size n. Which asymptotic notation best describes its worst-case time complexity?

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 39

What is a primary challenge in analyzing the space complexity of algorithms using dynamic data structures?

Accepted Answer

Unpredictable memory usage patterns in dynamic data structures.

Answer

Space complexity analysis only accounts for the algorithm's main operations.

Answer

Asymptotic analysis is not applicable to algorithms with dynamic data structures.

Question 40

Which of the following best represents the time complexity of a linear search algorithm operating on an array of size n?

Accepted Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Answer

O(1)

Question 41

Consider an algorithm that searches for a specific element in a sorted array of size n using binary search. What is its time complexity?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Question 42

Which of the following is NOT a valid asymptotic notation used to describe the growth rate of algorithms?

Accepted Answer

O(n!)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 43

Which data structure typically offers constant-time complexity for insertion and deletion operations?

Accepted Answer

Hash Table

Answer

Linked List

Answer

Binary Search Tree

Answer

Array

Question 44

An algorithm with time complexity f(n) = n^2 + 2n + 1 belongs to which time complexity class?

Accepted Answer

O(n^2)

Answer

O(1)

Answer

O(n)

Answer

O(n log n)

Question 45

Which of the following is a common technique for analyzing the worst-case time complexity of an algorithm?

Accepted Answer

Master theorem

Answer

Brute force testing

Answer

Heuristic estimation

Answer

Amortized analysis

Question 46

The space complexity of an algorithm measures the:

Accepted Answer

Amount of additional memory required to run the algorithm

Answer

Time taken by the algorithm to complete its execution

Answer

Number of instructions executed by the algorithm

Question 47

Which of the following algorithms has the lowest space complexity?

Accepted Answer

In-place sorting

Answer

Binary search

Answer

Bubble sort

Answer

Merge sort

Question 48

Asymptotic analysis allows us to:

Accepted Answer

Compare the efficiency of algorithms as the input size grows infinitely large

Answer

Predict the exact time an algorithm will take to execute

Answer

Determine the worst-case scenario for an algorithm

Question 49

Which of the following asymptotic notations indicates that the function grows more slowly than any exponential function?

Accepted Answer

o(2^n)

Answer

Θ(n)

Answer

ω(n)

Answer

Ω(n)

Question 50

Algorithm A has a time complexity of O(3^n) and algorithm B has a time complexity of O(n^3). Which algorithm is more efficient for large inputs?

Accepted Answer

Algorithm B

Answer

They are equally efficient

Answer

Algorithm A

Answer

Cannot be determined

Question 51

Which of the following algorithms uses greedy approach to achieve its efficiency?

Accepted Answer

Kruskal's algorithm

Answer

Selection sort

Answer

Bubble sort

Answer

Insertion sort

Question 52

Dynamic programming is an algorithm design paradigm that:

Accepted Answer

Stores and reuses intermediate results

Answer

Divides the problem into independent subproblems

Answer

Uses recursion to solve problems