Design and Analysis of Algorithms

Which of the following best describes space complexity?
(i) Time taken by the algorithm
(ii) Memory required to run an algorithm
(iii) Number of recursive calls
(iv) Number of loops used

Which property of an algorithm ensures that every step is clear and has exactly one meaning?

(i) Finiteness
(ii) Effectiveness
(iii) Definiteness
(iv) Generality

Which of the following notations is used to represent the worst-case time complexity of an algorithm?
(i) O-notation
(ii) $\Omega$-notation
(iii) $\Theta$-notation
(iv) $\delta$-notation

An algorithm is made up of two independent time complexities $f(n)$ and $g(n)$. Then the complexities of the algorithm is in the order of
(i) $f(n) \times g(n)$
(ii) $\max \{ f(n), g(n) \}$
(iii) $\min \{ f(n), g(n) \}$
(iv) $f(n) + g(n)$

If an algorithm has time complexity $T(n) = 5n^2 + 3n + 7$, its asymptotic upper bound is:
(i) $O(n)$
(ii) $O(n^2)$
(iii) $O(n \log n)$
(iv) $O(n^3)$

In Asymptotic notation, Big- $\Omega$ (Omega) is used to represent

(i) The upper bound (Worst-case)
(ii) The lower bound (Best-case)
(iii) The tight bound (Average-case)
(iv) None of the above

The recurrence $T(n) = T(n/2) + 1$ has a time complexity of:
(i) $O(n)$
(ii) $O(\log n)$
(iii) $O(n \log n)$
(iv) $O(n^2)$

Which sorting algorithm is considered stable and has a time complexity of $O(n^2)$?
(i) Quick sort
(ii) Merge sort
(iii) Insertion sort
(iv) Selection sort

What is the complexity of $T(n) = 2T(n/4) + n^2 \log n$?
(i) $\Theta(n^2 \log(\log n))$
(ii) $\Theta(n^3 \log n)$
(iii) $\Theta(n^2 \log n)$
(iv) $\Theta(n \log n)$

Which one of the following functions is asymptotically smallest?
(i) $2^n$
(ii) $n^{\log n}$
(iii) $n^{\sqrt{n}}$
(iv) $(100)^{(\log n)^{1/3}} + (\log \log n)^{2/3}$

In algorithm analysis, what does "space complexity" refer to?
(i) The number of input elements
(ii) The amount of physical memory used
(iii) The number of recursive calls
(iv) The number of lines of code in the algorithm

The average number of comparisons performed by merge sort algorithm in merging two sorted lists of 2 elements is
(i) 8/5
(ii) 11/7
(iii) 11/6
(iv) 8/3

Explain the concept of asymptotic notation (Big O, Big Omega, and Big Theta) in algorithm analysis.

Answer the following:
(i) Differentiate between best-case, worst-case, and average-case complexity with suitable examples.
(ii) Use examples like linear search to demonstrate the differences.
(iii) Discuss why worst-case analysis is often preferred in practice.

Solve the following recurrence by successive substitution method:
$$f(1) = 1 \quad \text{if } n=1$$
$$f(n) = 3f(n/2) + 6 \quad \text{if } n > 1$$

Consider the following recurrence relation:
$$T(n) = 2T(n/2) + n$$
Use the substitution method to find an asymptotic upper bound for the function $T(n)$.

Suppose the number of basic operations in an algorithm is defined as: $T(n) = T(n-1) + n$, with $T(1) = 1$.
Solve this recurrence using the substitution method and determine the time complexity.

Define time complexity and space complexity. Write an algorithm for adding n natural numbers and find the space required by that algorithm.

Apply the Master Theorem to determine the time complexity of the following recurrence relations.
(i) $T(n) = 4T(n/2) + n^3$
(ii) $T(n) = T(n/2) + 2^n$

What is the Master's Theorem? State the general form and the three cases of the theorem. Use it to solve the following recurrence relations:
(i) $T(n) = 2T(n/2) + n$
(ii) $T(n) = 3T(n/2) + n^2$
(iii) $T(n) = 2T(n/2) + n/\log n$
Explain which case applies in each situation.

Discuss the concepts of asymptotic notations and its properties.

Apply the Linear Search algorithm to find the position of the target element 7 in the following array: $A=[3, 5, 2, 8, 7, 1, 4]$. Also, analyze the time and space complexity.

State master's theorem and find the time complexity for the following recurrence:
$T(n) = 2T(n^{1/2}) + \log n$

Write short notes on any two of the following:
(i) Asymptotic Notations
(ii) Clique decision problem
(iii) Max-flow-min-cut theorem
(iv) Union-Find Algorithm

Write a short note on:

Recursion tree method

Write a short note on:

Asymptotic Notations