Page 27 - Data Structures Interactive Book

2.5 Exercise

Essay Questions
1. Define time complexity and explain why it is important in algorithm analysis.

2. Write a program in C++ to implement linear search and analyze its best, worst, and

average case performance.
3. Compare the time complexity of bubble sort and binary search.

4. Explain the difference between constant time ( )and logarithmic time ( ⁡ )with

examples.

Multiple Choice Questions (MCQ)

Q1. What does time complexity measure in an algorithm?

a) The amount of memory used
b) The number of steps relative to input size

c) The programming language efficiency
d) The speed of the computer processor

Q2. What is the worst-case time complexity of linear search?

a) ( ) ⁡⁡⁡⁡⁡⁡b) ( ) c) ( ) d) ( )
Q3. Which of the following has better average-case performance for searching in a sorted
array?
a) Linear Search b) Binary Search c) Bubble Sort d) Selection Sort

Q4. What is the time complexity of Bubble Sort in the worst case?

a) ( ) b) ( ⁡ ) c) ( ) d) ( )
Q5. Which of the following is an example of constant time ( )?

a) Accessing an element in an array by index

b) Performing binary search in a sorted array

c) Traversing a linked list of size

d) Sorting an array using Merge Sort
Q6. Which of the following correctly describes logarithmic time ( ⁡ )?

a) The algorithm’s runtime doubles when input size doubles

b) The algorithm’s runtime increases linearly with input size
c) The algorithm’s runtime increases slowly, proportional to the log of input size

d) The algorithm’s runtime remains constant regardless of input size

27