22CS404-Analysis of Algorithms Assessment

Name of the Student

Register Number

Year/Sem

Class/Section

1. What does the time complexity of an algorithm represent?

• A) The amount of memory used
• B) The number of inputs
• C) The running time as a function of input size
• D) The number of programmers needed

2. Which of the following is the correct asymptotic notation for the best case performance of an algorithm?

• A) Θ (Theta)
• B) Ω (Omega)
• C) O (Big-O)
• D) o (Little-o)

3. What is the time complexity of the recurrence: T(n) = T(n/2) + O(1)?

• A) O(n)
• B) O(log n)
• C) O(n log n)
• D) O(n²)

4. Which method uses expansion to solve recurrence relations?

• A) Master Theorem
• B) Recurrence Tree
• C) Iteration Method
• D) Substitution Method

5. What is the time complexity of Merge Sort?

• A) O(n)
• B) O(n²)
• C) O(n log n)
• D) O(log n)

6.Which class includes problems that can be verified in polynomial time but not necessarily solved in polynomial time?

• A) P
• B) NP
• C) NP-Complete
• D) EXP