UNIT 1 – SHORT ANSWERS
1. Algorithm: Step-by-step procedure to solve a problem.
Characteristics: Input, Output, Definiteness, Finiteness, Effectiveness.
2. Time Complexity: Time taken by algorithm.
Space Complexity: Memory used.
3. Recursion vs Non-recursion:
Recursion: function calls itself.
Non-recursion: uses loops.
4. Notations: Big-O, Big-Omega, Big-Theta.
5. Linear Search: Best O(1), Avg O(n), Worst O(n)
Binary Search: Best O(1), Avg O(log n), Worst O(log n)
6. Asymptotic Notations: O, Ω, Θ
7. Bubble Sort: Best O(n), Avg O(n²), Worst O(n²)
8. Insertion Sort: Best O(n), Avg O(n²), Worst O(n²)
9. Selection Sort: Best O(n²), Avg O(n²), Worst O(n²)
10. Data Structures: Linear (Array, Stack), Non-linear (Tree, Graph)
11. Linear vs Non-linear: Sequence vs Hierarchical
12. Static vs Dynamic: Fixed (Array) vs Changeable (Linked List)
13. Operations: Insertion, Deletion, Traversal, Searching, Sorting
14. Recursion Algorithms: Factorial, Fibonacci, Binary Search
15. Space Complexity: O(1)
16. O(1): constant, O(n): loop
17. Pseudocode Advantages: Easy, language independent
UNIT 1 – LONG ANSWERS
1. Asymptotic Notations:
Big-O (worst), Omega (best), Theta (exact)
2. Factorial:
Time O(n), Space O(n)
3. 3n²+2n+1: O(n²)
4. Amortized:
Aggregate, Accounting
5. Performance:
Time & Space, Best/Avg/Worst
6. Student Algorithm:
Input, store, display
7. Nested loops:
Time O(n²), Space O(1)
8. Binary Search:
Best O(1), Avg/Worst O(log n)
9. Bubble Sort:
Best O(n), Avg/Worst O(n²)
10. Linear Search:
Best O(1), Avg/Worst O(n)
11. Matrix Multiplication:
O(n³)