Design & Analysis of Algorithm
(** Please go through the textbook Once. **)
Q1. Show that : 5n^37n-4=O(n^3)
Sol:
Q2. Explain the core idea behind the exhaustive search technique.
Sol:
Exhaustive Search is a brute-force method that tries all possible solutions to a
problem.
Approach:
● Generate every possible combination or arrangement.
● Test each one to see if it satisfies the condition.
● Return the best or first valid solution.
The key idea is to just check everything without shortcuts
It is used when problem size is small or limited, and when no better method is
known.
Used in problems like:
● Travelling Salesman Problem
● Knapsack Problem
● Password cracking
Q3. Describe mathematical techniques to analyze the time complexity of a given
non-recursive algorithm.
Sol:
Count how many times key operations (like addition, assignment) are executed.
Analyze Loops
● Single loop → O(n)
● Nested loop → O(n²)
● Logarithmic loop → O(log n)
Keep the highest degree term only. Ignore Constants and Lower Terms
● Example: 2n² + 3n + 1 → O(n²)
Represent time complexity using O, Ω, and Θ notations.
Consider Best, Worst, and Average cases.
Use Summation formulas wherever necessary:
● Sum of first n natural numbers:
●
Eg for calculating complexity:
Loop runs n times, so the time complexity would be O(n).
Q4. Describe the essential components of an algorithm specification.
Sol:
1. Input
● Specifies the data given to the algorithm.
● Example: An array of n numbers.
2. Output
● Describes what the algorithm should return or produce.
● Example: The sorted version of the input array.
3. Definiteness
● Every step must be precisely and unambiguously defined.
4. Finiteness
● The algorithm must complete in a finite number of steps.
5. Effectiveness
● Each operation must be basic enough to be carried out by hand or computer.
6. Correctness
● The algorithm should solve the problem as intended and produce the right
output.
7. Efficiency (Time and Space)
● Consider how much time and memory the algorithm uses.
Q5. Perform insertion sort on the following data: 23,34,65,87,19,51,64
Sol:
Q6. Define time and space complexity. Give an example of how both affect
algorithm efficiency.
Sol:
1. Time Complexity:
● It measures the amount of time an algorithm takes to complete based on the
size of input n.
● Expressed using Big-O notation like O(1), O(n), O(n²), etc.
● While analyzing the complexity we always consider the worst case.
2. Space Complexity:
● It measures the amount of memory (space) an algorithm uses during its
execution, including input, output, and auxiliary space.
Eg:
● Time Complexity: O(n) → loop runs n times
● Space Complexity: O(1) → only variable i is used
Impact on Efficiency:
● If time complexity is high (e.g., O(n³)), the algorithm is slow for large
inputs.
● If space complexity is high, it uses too much memory, which may cause
crashes or slowdowns.
Q7. Apply the Selection Sort algorithm to arrange a given list of elements in
ascending order. 34,12,87,22,67,43,56,19
Sol:
Q8. Determine the asymptotic time complexity of a given brute-force algorithm.
Sol:
1. Understand the algorithm steps
● Identify the operations and how many times they run depending on input
size n.
2. Count the loops
● Check how many times each loop runs (usually depends on input size n).
3. Analyze work done inside loops
● Check if the inner operations are constant time (O(1)) or more.
4. Add all parts together
● Add the time of all parts together if there are multiple steps.
5. Express using Big-O notation
● Keep only the highest order term, ignore constants and smaller terms.
Eg for a brute-force algorithm with two nested loops each running from 1 to
n:
● Outer loop: runs n times
● Inner loop: runs n times for each outer loop iteration
● Total operations: n × n = n²
● Time Complexity = O(n²)
Q9. Compare and contrast the space and time complexities of Sequential Search
and Selection Sort.
Sol:
Sequential Search:
● Time Complexity (Best Case): O(1) → if element is at the beginning.
● Time Complexity (Worst Case): O(n) → if element is at the end or not
present.
● Space Complexity: O(1) → only a few variables used, no extra memory.
Selection Sort:
● Time Complexity (Best, Average, Worst Case): O(n²) → always compares
all pairs.
● Space Complexity: O(1) → sorts in-place, uses constant extra space.
Key Comparison:
● Sequential Search is faster on average than Selection Sort.
● Both use constant space, but Selection Sort is much slower due to nested
loops.
● Sequential Search is used for finding elements, while Selection Sort is used
for arranging data.
Q10. Illustrate the process of the String Matching algorithm to find a pattern within
a text.
Sol:
● Start from the beginning of the text.
● Compare the pattern with a substring of the text (same length as the pattern).
● If all characters match, a pattern is found.
● If not, move one step forward in the text and repeat the comparison.
● Continue until the end of the text is reached or a match is found.
Q11. Classify the different types of problems that can be effectively solved using
algorithmic approaches.
Sol:
● Sorting Problems – Arrange elements in order (e.g., Merge Sort, Quick
Sort).
● Searching Problems – Locate a specific element in data (e.g., Linear
Search, Binary Search).
● Graph Problems – Solve on nodes and edges like shortest path or MST
(e.g., Dijkstra’s, Prim’s).
● Optimization Problems – Find the most efficient or best solution (e.g.,
Knapsack, TSP).
● Dynamic Programming – Use results of subproblems to build the final
solution (e.g., LCS, Fibonacci).
● Greedy Problems – Make locally optimal choices at each step (e.g.,
Activity Selection, Huffman Coding).
● Backtracking Problems – Explore all possibilities and backtrack if needed
(e.g., N-Queens, Sudoku).
● Divide and Conquer – Break problems into parts, solve, and combine (e.g.,
Merge Sort, Quick Sort).
● Brute Force Problems – Try all combinations until a solution is found (e.g.,
Password cracking).
● String Matching Problems – Find patterns in text (e.g., KMP, Naive
Matching).
Q12. Demonstrate the step-by-step execution of the Brute-Force Sequential Search
algorithm on a sample dataset.
Sol:
Q13. Explain insertion sort algorithm and analyze it.
Sol:
Q14. Explain the fundamental characteristics that define an algorithm.
Sol:
● Finiteness: It must finish after a limited number of steps.
● Input: It takes zero or more inputs.
● Output: It produces at least one output.
● Definiteness: Each step is clearly and precisely defined.
● Effectiveness: Each step can be performed exactly and in finite time.
● Generality: It works for all valid inputs of the problem.
Q15. Analyze the worst-case scenario for the Sequential Search algorithm.
Sol:
Q16. Categorize common algorithm efficiency classes based on their growth rates.
Sol:
Constant Time – O(1):
Time doesn’t change with input size.
Example: Accessing an element in an array.
Logarithmic Time – O(log n):
Time increases slowly as input size grows.
Example: Binary Search.
Linear Time – O(n):
Time increases directly with input size.
Example: Traversing an array.
Linearithmic Time – O(n log n):
Faster than quadratic but slower than linear.
Example: Merge Sort, Heap Sort.
Quadratic Time – O(n²):
Time grows with the square of input size.
Example: Bubble Sort, Insertion Sort.
Cubic Time – O(n³):
Time grows with a cube of input size.
Example: Matrix multiplication (basic).
Exponential Time – O(2ⁿ):
Time doubles with each additional input.
Example: Solving Tower of Hanoi, Backtracking (N-Queen).
Factorial Time – O(n!):
Very slow growth; infeasible for large inputs.
Example: Brute-force solution to TSP.
Q17. Explain Big-O, Big-Omega, and Big-Theta asymptotic notations with
examples.
Sol:
1. Big O - Worst case
● Big-O gives the upper bound of an algorithm's running time.
● It describes the maximum time the algorithm could take.
Eg:
arr[] = [1, 4, 5, 2] , key = 3
In linear search the key 3 not found in the array.
2. Big Ohmega - Best case
● Big-Omega gives the lower bound of the running time.
● It describes the best-case scenario of the algorithm.
Eg:
arr[] = [1, 4, 5, 2] , key = 1
In linear search the key found in index 0 that is at position 1
3. Big Theta - Average case
● Big-Theta gives a tight bound — both upper and lower bound.
● It describes the average or exact time for typical inputs.
Eg:
Arr[] = [1, 4, 5, 2] , key = 5
In linear search the key found in index 3 somewhere in the between
Q18. Outline the distinct steps involved in the algorithm design and analysis
process.
Sol:
1. Problem Definition
Clearly understand the problem requirements and constraints.
2. Input/Output Specification
Define what inputs the algorithm takes and what output it should produce.
3. Choose Design Technique
Select an appropriate strategy: Greedy, Divide and Conquer, Dynamic
Programming, etc.
4. Design the Algorithm
Step-by-step logical procedure to solve the problem.
5. Prove Correctness
Ensure the algorithm always gives the correct output for all valid inputs.
6. Analyze Time and Space Complexity
Determine how the algorithm’s resource usage grows with input size.
7. Optimize (if needed)
Improve the algorithm’s efficiency based on analysis.
8. Implement and Test
Write code and test on different cases to verify correctness and performance.
Q19. Apply the String Matching algorithm to a specific text and pattern,
highlighting the comparisons made. Text: bitty_bought_some_sweet_mangoes.
Pattern:mango
Sol:
Q20. Differentiate between space complexity and time complexity in the context of
algorithm performance.
Sol:
Time Complexity:
● Measures the amount of time an algorithm takes to run based on input size.
● Indicates the number of operations or steps performed.
● Helps analyze how execution time grows as input size increases.
● Important for understanding the speed and efficiency of an algorithm.
Space Complexity:
● Measures the amount of memory an algorithm uses during execution.
● Includes space for input, variables, and any extra data structures.
● Helps analyze how memory requirements grow with input size.
● Important for evaluating the algorithm’s memory usage.