Algorithm Analysis - Questions and Answers
### 1. Introduction to Algorithm Analysis
1. What is a data structure, and why is it important in computing?
- A data structure is a systematic way of organizing and accessing
data. It helps in efficiently storing, retrieving, and managing data in
computing applications.
2. Define an algorithm and explain its key characteristics.
- An algorithm is a step-by-step, unambiguous procedure for
performing a task in a finite amount of time.
- Key characteristics:
- Unambiguous: Each step is clearly defined.
- Finite: It must complete in a limited number of steps.
- Well-defined input and output.
3. Why do we analyze algorithms? List two main criteria for judging
algorithms.
- We analyze algorithms to compare different solutions and
determine efficiency in terms of time and space.
- Two main criteria:
1. Correctness: Does the algorithm provide the correct solution in
a finite number of steps?
2. Efficiency: How much memory and time does it require?
4. What is algorithm efficiency, and how is it measured?
- Algorithm efficiency refers to the computational resources
required to execute an algorithm.
- It is measured using time complexity (running time) and space
complexity (memory usage).
### 2. Running Time Analysis
5. What is running time analysis, and why is it important?
- Running time analysis determines how processing time increases
as input size grows.
- It predicts how an algorithm will perform for large inputs.
6. List three different types of input sizes that affect an algorithm's
running time.
- Size of an array
- Polynomial degree
- Number of elements in a matrix, graph vertices, or edges
7. What are some limitations of experimental algorithm analysis?
- Difficult to compare algorithms unless tested on the same
hardware/software.
- Can only be tested on a limited set of inputs.
- Requires full implementation before analyzing.
### 3. Comparing Algorithms: Beyond Experimental Analysis
8. What is the purpose of counting primitive operations in an
algorithm?
- It helps estimate running time without execution by counting basic
operations.
9. How can we measure an algorithm's efficiency without
implementing it?
- By using asymptotic analysis, which examines how operations
grow with input size.
10. Define worst-case, best-case, and average-case analysis.
- Worst-case: Slowest execution for the most unfavorable input.
- Best-case: Fastest execution for the most favorable input.
- Average-case: Expected execution time over random inputs.
### 4. Asymptotic Analysis
11. What is asymptotic analysis, and why is it useful?
- It analyzes algorithm growth as input size increases, ignoring
constants and lower terms.
- It compares algorithms independently of hardware/software
environments.
12. Name the three notations used in asymptotic analysis.
- Big-O (O)
- Big-Omega (Omega)
- Big-Theta (Theta)
13. Define Big-O notation and explain its purpose.
- Big-O (O) represents the upper bound of an algorithm's growth
rate.
14. What does it mean when we say a function is O(n²)?
- It means the algorithm's running time grows at most proportional
to n² for large inputs.
15. Give an example of a function that is O(n³) and justify why.
- Example: f(n) = 4n³ + 2n + 7
- Justification: The highest-degree term (4n³) dominates for large n,
so we ignore lower-order terms and constants, giving O(n³).
