Algorithm Analysis: Master Algorithm Efficiency for ICT Year 13

Question 1

Which of the following time complexities correctly represents the performance of the bubble sort algorithm?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(2^n)

Question 2

What is the primary goal of profiling an algorithm?

Accepted Answer

To locate performance bottlenecks

Answer

To optimize memory allocation

Answer

To improve code readability

Answer

To enhance security measures

Question 3

Which of the following algorithms is considered a heuristic?

Accepted Answer

Genetic algorithm

Answer

Dijkstra's algorithm

Answer

Breadth-first search

Answer

Bellman-Ford algorithm

Question 4

Which of the following is a valid time complexity notation representing constant time regardless of input size?

Accepted Answer

O(1)

Answer

O(n2)

Answer

O(x)

Answer

O(log2(n))

Question 5

An algorithm with a time complexity of O(n) performs how many iterations?

Accepted Answer

A number of iterations that grows linearly with the input size

Answer

A fixed number of iterations

Answer

A number of iterations that grows quadratically with the input size

Answer

A number of iterations that grows exponentially with the input size

Question 6

What is the space complexity of an algorithm that creates an array of size n?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n2)

Answer

O(log2(n))

Question 7

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

Accepted Answer

Computing the factorial of a number

Answer

Sorting a list of n elements

Answer

Searching for a specific element in a binary search tree

Answer

Finding the shortest path in a graph

Question 8

What is the time complexity of an algorithm that iterates over a linked list of length n?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log2(n))

Answer

O(n2)

Question 9

An algorithm that runs in O(n3) time is considered to be:

Accepted Answer

Inefficient

Answer

Efficient

Answer

Optimal

Answer

Suboptimal

Question 10

Which of the following algorithms is designed to find the shortest path between two nodes in a weighted, directed graph?

Accepted Answer

Dijkstra's Algorithm

Answer

Prim's Algorithm

Answer

Kruskal's Algorithm

Answer

Bellman-Ford Algorithm

Question 11

What is the space complexity of a queue data structure, assuming each element in the queue occupies a constant amount of space?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 12

What is the Big O notation representing the worst-case time complexity of an algorithm that performs n^2 steps?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(log n)

Answer

O(1)

Question 13

An algorithm with time complexity O(n^2) means that:

Accepted Answer

The time taken increases quadratically with the number of elements.

Answer

The time taken increases linearly with the number of elements.

Answer

The time taken is independent of the number of elements.

Answer

The time taken decreases exponentially with the number of elements.

Question 14

Which of the following is a space-efficient data structure that stores data in a key-value pair format?

Accepted Answer

Hash table

Answer

List

Answer

Tree

Answer

Queue

Question 15

An algorithm with space complexity O(log n) means that:

Accepted Answer

The space required grows logarithmically with the number of elements.

Answer

The space required is constant, regardless of the number of elements.

Answer

The space required grows linearly with the number of elements.

Answer

The space required grows exponentially with the number of elements.

Question 16

Which of the following is a disadvantage of using recursion in algorithm design?

Accepted Answer

Can lead to stack overflows

Answer

Difficult to debug

Answer

Inefficient for small datasets

Answer

Not suitable for iterative tasks

Question 17

An algorithm that finds the maximum value in an unsorted array can have a time complexity of:

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 18

An algorithm with time complexity O(1) is known as:

Accepted Answer

Constant-time algorithm

Answer

Linear-time algorithm

Answer

Logarithmic-time algorithm

Answer

Polynomial-time algorithm

Question 19

Which of the following algorithms is known for its greedy approach?

Accepted Answer

Dijkstra's algorithm

Answer

Bubble sort

Answer

Binary search

Answer

Merge sort

Question 20

What is the main purpose of analyzing an algorithm's time complexity?

Accepted Answer

To understand how an algorithm's running time changes as the input size gets very large.

Answer

To calculate the exact time an algorithm takes for a specific input.

Answer

To find the least number of steps an algorithm needs to complete its task.

Answer

To determine the worst possible time an algorithm could take for any input.

Question 21

Consider an algorithm that sorts an array of n elements using the bubble sort technique. What is the worst-case time complexity of this sorting algorithm?

Accepted Answer

O(n^2): O of n square

Answer

O(n log n): O of n log n

Answer

O(n^3): O of n cube

Answer

O(2^n): O of 2 to the power of n

Question 22

Consider an algorithm that calculates the factorial of a given number n. What is the time complexity of this algorithm?

Accepted Answer

O(n!): Factorial time Complexity

Answer

O(1): Constant time Complexity

Answer

O(log n): Logarithmic time Complexity

Answer

O(n): Linear time Complexity

Question 23

Consider an algorithm that generates all possible subsets of a set of n elements. What is the time complexity of this algorithm?

Accepted Answer

O(2^n): Exponential time Complexity

Answer

O(n): Linear time Complexity

Answer

O(n log n): O of n log n

Answer

O(n!): Factorial time Complexity

Question 24

Which of the following is a measure of the efficiency of an algorithm in terms of how quickly it can solve a problem of a given size?

Accepted Answer

Time complexity

Answer

Space complexity

Answer

Auxiliary space

Answer

Constant factor

Question 25

Which of the following is NOT a type of asymptotic analysis used to assess algorithm efficiency?

Accepted Answer

Minimax

Answer

Big O Notation

Answer

Amortized Analysis

Question 26

When analyzing the efficiency of an algorithm, a key factor to consider is:

Accepted Answer

Input size

Answer

Hardware specifications

Answer

Programming language used

Answer

Temperature of the environment

Question 27

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

Accepted Answer

Bubble sort

Answer

Binary search

Answer

Merge sort

Answer

Quick sort

Question 28

What is the best way to represent the relationship between the number of operations performed by an algorithm and the size of its input?

Accepted Answer

Time complexity notation (e.g., O())

Answer

Linear equation

Answer

Flowchart

Answer

Pseudo-code

Question 29

Which of the following statements about space complexity is true?

Accepted Answer

It refers to the amount of memory required by an algorithm while executing

Answer

It is independent of the size of the input

Answer

It can be measured in terms of the number of instructions executed

Answer

It is always constant for a given algorithm

Question 30

What is the asymptotic time complexity of an algorithm that performs a fixed number of operations for each input size?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 31

What is the space complexity of the following algorithm?

for i = 1 to n:
	 for j = 1 to n:
		 print(i, j)

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(log n)

Answer

O(1)

Question 32

Which of the following is a key difference between time and space complexity?

Accepted Answer

Time complexity measures the number of operations, while space complexity measures the amount of memory used.

Answer

Time complexity is always worse than space complexity.

Answer

Space complexity is only considered when dealing with large datasets.

Answer

Time complexity is more important than space complexity.

Question 33

What is the benefit of using Big O notation?

Accepted Answer

It allows us to compare algorithms without considering specific hardware or software.

Answer

It provides an exact measure of the number of operations an algorithm will perform.

Answer

It helps optimize algorithms for specific input sizes.

Answer

It can be used to predict the memory usage of an algorithm.

Question 34

What is the primary goal of algorithm analysis?

Accepted Answer

To predict the performance of an algorithm.

Answer

To identify the most efficient algorithm for a given problem.

Answer

To improve the readability and maintainability of algorithms.

Answer

To reduce the memory usage of algorithms.

Question 35

Which of the following best describes the time complexity of an algorithm that compares two sorted arrays of size n?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Question 36

An algorithm's space complexity is denoted as O(1). What does this imply?

Accepted Answer

The algorithm requires constant memory, regardless of input size.

Answer

The algorithm's memory usage grows logarithmically with input size.

Answer

The algorithm's memory usage grows linearly with input size.

Answer

The algorithm's memory usage is exponential to input size.

Question 37

What is the primary purpose of using asymptotic notation in algorithm analysis?

Accepted Answer

To approximately describe an algorithm's performance for sufficiently large inputs.

Answer

To precisely quantify an algorithm's performance for all input sizes.

Answer

To compare the efficiency of different algorithms for a given input size.

Answer

To determine the maximum time complexity of an algorithm.

Question 38

What is the fundamental distinction between time complexity and space complexity?

Accepted Answer

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

Answer

Space complexity measures execution time, while time complexity measures memory usage.

Answer

Time complexity and space complexity are identical concepts.

Answer

Time complexity pertains to iterative algorithms, while space complexity pertains to recursive algorithms.

Question 39

Which of the following measures the time required for an algorithm to complete its task?

Accepted Answer

Time complexity

Answer

Space complexity

Answer

Auxiliary space

Answer

Input size

Question 40

An algorithm with a time complexity of O(n log n) performs:

Accepted Answer

Faster than linearly but slower than exponentially

Answer

Linearly as the input size increases

Answer

Exponentially as the input size increases

Answer

Slower than n

Question 41

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

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Question 42

An algorithm that stores temporary values outside its main data structure has:

Accepted Answer

Auxiliary space

Answer

Constant space

Answer

Input-dependent space

Answer

Linear space

Question 43

An algorithm with a time complexity of O(1) is known as:

Accepted Answer

Constant

Answer

Linear

Answer

Quadratic

Answer

Exponential

Question 44

What is a limitation of time complexity analysis?

Accepted Answer

It ignores constant factors

Answer

It doesn't consider the size of the input

Answer

It only works for deterministic algorithms

Answer

It requires the algorithm to be fully implemented

Question 45

An algorithm with a space complexity of O(n^2) requires:

Accepted Answer

Quadratic memory

Answer

Constant memory

Answer

Linear memory

Answer

Logarithmic memory

Question 46

Which data structure has a worst-case time complexity of O(log n) for both insertion and search operations?

Accepted Answer

Binary search tree

Answer

Array

Answer

Linked list

Answer

Hash table

Question 47

What is the process of reducing the running time of an algorithm while increasing its space consumption known as?

Accepted Answer

Space-time tradeoff

Answer

Dynamic programming

Answer

Divide-and-conquer

Answer

Greedy algorithm

Question 48

Which of the following is NOT a valid Big-O notation for time complexity analysis?

Accepted Answer

O(n^0.5)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 49

An algorithm with a time complexity of O(2^n) indicates that:

Accepted Answer

The algorithm runs exponentially fast.

Answer

The algorithm runs in linear time.

Answer

The algorithm will never complete.

Answer

The algorithm is highly efficient.

Question 50

Which sorting algorithm has the best average-case and worst-case time complexity of O(n log n)?

Accepted Answer

Merge sort

Answer

Bubble sort

Answer

Selection sort

Answer

Quicksort

Question 51

Consider an algorithm that merges two sorted arrays. What is its average-case time complexity?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(n^3)

Question 52

Which of the following accurately measures the execution time of an algorithm?

Accepted Answer

Time complexity

Answer

Space complexity

Answer

Algorithm efficiency

Answer

Code complexity

Question 53

Determine the space complexity of an algorithm that creates a duplicate of the input array:

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Question 54

For the algorithm: for i in range(n): for j in range(i): print(i, j), what is its worst-case time complexity?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n^3)

Answer

O(log n)

Question 55

Which factor does NOT influence algorithm efficiency?

Accepted Answer

Programming language

Answer

Input size

Answer

Algorithm design

Answer

Hardware specifications

Question 56

Which algorithm efficiently searches for an element in a sorted array?

Accepted Answer

Binary search

Answer

Linear search

Answer

Breadth-first search

Answer

Depth-first search

Question 57

Which data structure offers the most efficient insertion and deletion operations?

Accepted Answer

Linked list

Answer

Array

Answer

Stack

Answer

Queue

Question 58

Which of the following is NOT a parameter of algorithm analysis?

Accepted Answer

Number of cycles needed to execute the algorithm

Answer

Time complexity

Answer

Space complexity

Answer

Asymptotic lower bound

Question 59

An algorithm with a time complexity of O(n) is said to be:

Accepted Answer

Linear time

Answer

Constant time

Answer

Quadratic time

Answer

Exponential time

Question 60

Which of the following represents the worst-case time complexity of a binary search?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 61

Space complexity pertains to:

Accepted Answer

The amount of memory used by an algorithm

Answer

The number of instructions executed by an algorithm

Answer

The time taken for an algorithm to run

Answer

The input size of an algorithm

Question 62

An algorithm that requires additional memory proportional to the input size has a space complexity of:

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 63

Which of the following data structures has a space complexity of O(1)?

Accepted Answer

Array

Answer

Linked list

Answer

Binary search tree

Answer

Hash table