Time Complexity Analysis: Master the Fundamentals for Efficient Algorithms

Question 1

Which of the following is the correct asymptotic notation for an algorithm that takes O(n^2) time?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(2^n)

Question 2

Which of the following data structures has the best time complexity for searching an element?

Accepted Answer

Hash Table

Answer

Array

Answer

Linked List

Answer

Binary Search Tree

Question 3

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

Accepted Answer

Bubble Sort

Answer

Merge Sort

Answer

Quick Sort

Answer

Heap Sort

Question 4

What is the time complexity of an algorithm that iterates over an array of length n and performs a constant-time operation on each element?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 5

Which of the following functions has a time complexity of O(log n)?

Accepted Answer

Binary search

Answer

Linear search

Answer

Bubble sort

Answer

Selection sort

Question 6

What is the asymptotic notation for an algorithm that takes O(2^n) time?

Accepted Answer

O(2^n)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 7

Which of the following data structures supports efficient insertion and deletion operations at any position?

Accepted Answer

Linked List

Answer

Array

Answer

Binary Search Tree

Answer

Hash Table

Question 8

What is the time complexity of an algorithm that iterates over a linked list of length n and performs a constant-time operation on each node?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 9

What is the time complexity of an algorithm that performs a recursive function call n times, where each function call takes constant time?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 10

What is the worst-case time complexity of the following Python code snippet? ```python def find_element(arr, target): for element in arr: if element == target: return True return False ```

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 11

Which of the following represents the time complexity of the bubble sort algorithm?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(log n)

Answer

O(n log n)

Question 12

Determine the asymptotic upper bound of the function f(n) = 2n^3 + 3n^2 + 5n + 1.

Accepted Answer

O(n^3)

Answer

O(n^2)

Answer

O(n)

Answer

O(1)

Question 13

Classify the following algorithm based on its time complexity: for i in range(n): for j in range(n): print(i, j).

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(log n)

Question 14

Determine the worst-case time complexity of the binary search algorithm.

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 15

Which of the following is not a common time complexity class?

Accepted Answer

O(2^n)

Answer

O(1)

Answer

O(n log n)

Answer

O(n^3)

Question 16

Explain the concept of 'amortized time complexity'.

Accepted Answer

The average time complexity over a series of operations.

Answer

The best-case time complexity for a specific operation.

Answer

The worst-case time complexity for a specific operation.

Answer

The time complexity of an operation without considering input.

Question 17

Calculate the time complexity of the following code snippet: for i in range(n): for j in range(1, n): print(i, j).

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(1)

Question 18

Calculate the time complexity of the nested loop below: ``` for i = 1 to n  for j = 1 to i     print(i, j) ```

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(log n)

Answer

O(n log n)

Question 19

Which algorithm has a constant time complexity, performing the same number of operations regardless of the input size?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 20

What is the time complexity of an algorithm that iterates through an array of size n, executing a fixed number of operations for each element?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 21

What is the time complexity of a binary search tree with a height of h?

Accepted Answer

O(log h)

Answer

O(1)

Answer

O(h)

Answer

O(n)

Question 22

Which approach is unlikely to be used for optimizing the time complexity of an algorithm?

Accepted Answer

Brute force

Answer

Divide and conquer

Answer

Memoization

Answer

Dynamic programming

Question 23

What is the time complexity of an algorithm that executes m operations for each of the n elements in an array?

Accepted Answer

O(m * n)

Answer

O(m)

Answer

O(n)

Answer

O(m + n)

Question 24

Identify an algorithm with exponential time complexity.

Accepted Answer

Towers of Hanoi

Answer

Linear Search

Answer

Binary Search

Answer

Bubble Sort

Question 25

What is the time complexity of an algorithm that finds all possible subsets of a set of size n?

Accepted Answer

O(2^n)

Answer

O(n)

Answer

O(n log n)

Answer

O(n!)

Question 26

Why is Big-O notation primarily used in algorithm analysis?

Accepted Answer

To provide a general idea of an algorithm's efficiency.

Answer

To precisely calculate an algorithm's running time for any input size.

Answer

To create algorithms with the best performance for specific problem sizes.

Question 27

An algorithm's time complexity is described as O(n). Which time complexity class does it fall under?

Accepted Answer

Linear

Answer

Constant

Answer

Logarithmic

Answer

Quadratic

Question 28

To find the maximum element in an unsorted array of size 'n', which algorithm would you use? Analyze its time complexity using the master method.

Accepted Answer

Linear Search

Answer

Binary Search

Answer

Merge Sort

Question 29

Which of the following accurately describes the time complexity of a sequential search on a sorted array of length n?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 30

What is the time complexity of an insertion sort algorithm for an array of length n?

Accepted Answer

O(n^2)

Answer

O(log n)

Answer

O(n)

Answer

O(n log n)

Question 31

Consider an algorithm that traverses an array of size n, performing a constant number of operations on each element. What is the time complexity of this algorithm?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 32

Which of the following best describes the time complexity of a binary search algorithm in the worst case?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 33

Consider an algorithm that recursively divides a problem until the subproblems reach a base case. If each recursive step reduces the problem size by a constant factor, what is the time complexity of this algorithm?

Accepted Answer

O(log n)

Answer

O(n^2)

Answer

O(n)

Answer

O(1)

Question 34

Which of the following accurately reflects the time complexity of inserting an element into a hash table?

Accepted Answer

O(1) on average

Answer

O(n^2)

Answer

O(log n)

Answer

O(n)

Question 35

Consider an algorithm that performs a depth-first search on a graph with n nodes and m edges. What is the worst-case time complexity of this algorithm?

Accepted Answer

O(n + m)

Answer

O(n)

Answer

O(n^2)

Answer

O(m)

Question 36

Which of the following is the time complexity of the merge sort algorithm for sorting a list of n elements?

Accepted Answer

O(n log n)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 37

Consider an algorithm that calculates the Fibonacci sequence using recursion. What is the time complexity of this algorithm?

Accepted Answer

O(2^n)

Answer

O(n)

Answer

O(1)

Answer

O(n log n)

Question 38

Which of the following statements about the time complexity of dynamic programming algorithms is accurate?

Accepted Answer

Depends on the specific problem being solved.

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 39

Consider an algorithm that traverses a doubly linked list, performing a set of constant-time operations on each node. What is the time complexity of this algorithm?

Accepted Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Answer

O(1)

Question 40

An algorithm has a time complexity of O(log n). What does this imply about its efficiency as the input size increases?

Accepted Answer

Its efficiency increases logarithmically.

Answer

Its efficiency increases quadratically.

Answer

Its efficiency increases exponentially.

Answer

Its efficiency increases linearly.

Question 41

Consider two algorithms with time complexities of O(n) and O(log n^2). Which algorithm is more efficient for sufficiently large inputs?

Accepted Answer

O(n)

Answer

Both algorithms are equally efficient.

Answer

O(log n^2)

Answer

Neither algorithm is more efficient without specific values of n.

Question 42

Which of the following substitutions is valid for simplifying a time complexity expression that includes the term n^2 + 2n?

Accepted Answer

O(n^2)

Answer

O(2n^2)

Answer

O(1)

Answer

O(n)

Question 43

An algorithm executes a set of operations with time complexity O(n) within a nested loop that iterates O(n) times. What is the overall time complexity of this algorithm?

Accepted Answer

O(n^2)

Answer

O(1)

Answer

O(log n)

Answer

O(n)

Question 44

An algorithm performs n arithmetic operations and m comparisons. Which of the following is the most appropriate time complexity class for this algorithm?

Accepted Answer

O(n + m)

Answer

O(m)

Answer

O(n)

Answer

O(n * m)

Question 45

Which of the following statements correctly describes the asymptotic behavior of an algorithm with time complexity O(2^n)?

Accepted Answer

It grows exponentially with the input size.

Answer

It grows linearly with the input size.

Answer

It remains constant regardless of the input size.

Answer

It grows logarithmically with the input size.

Question 46

Consider an algorithm that reads a file of size n and performs a binary search on it. What is the time complexity of this algorithm?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 47

Which of the following operations has a time complexity of O(1)?

Accepted Answer

Accessing an element of an array by index

Answer

Finding the maximum element in an unsorted array

Answer

Inserting an element into a linked list at the beginning

Answer

Reversing a singly linked list

Question 48

Consider an algorithm that merges two sorted arrays of sizes m and n. What is the time complexity of this algorithm?

Accepted Answer

O(m + n)

Answer

O(min(m, n))

Answer

O(m * n)

Question 49

Consider an algorithm that processes a singly linked list of length n. What is the time complexity of traversing the list and printing each element?

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(1)

Answer

O(n^2)

Question 50

Which of the following is NOT a factor that can affect the time complexity of an algorithm?

Accepted Answer

The programming language used

Answer

The efficiency of the algorithm

Answer

The implementation of the algorithm

Answer

The input size