Module 1 – Algorithms & Sorting
Design & Analysis of Algorithms
BCA Course
What is an Algorithm?
• Step-by-step procedure to solve a problem.
• Input
Input
→ Process → Output
Process Output
• Example: Find largest number in an array
Characteristics of Algorithms
• • Finiteness
• • Definiteness
• • Input
• • Output
• • Effectiveness
Analyzing Algorithms
• Measure efficiency: Time Complexity & Space
Complexity
• Example:
• - Linear Search = O(n)
• - Binary Search = O(log n)
Complexity of Algorithms
• Time Complexity: How fast algorithm runs
• Space Complexity: Memory used
• Example: Bubble Sort = O(n²)
Growth of Functions
• Asymptotic Notations:
• • Big-O (Upper bound)
• • Big-Ω (Lower bound)
• • Big-Θ (Tight bound)
• Example: Insertion Sort = O(n²)
Performance Measurement
• Compare algorithms using runtime vs input
size
• Example: Sorting 1000 numbers → Quick Sort
faster than Bubble Sort
Shell Sort
• Improves insertion sort using gaps
• Example Array: [23,12,1,8,34]
• Passes: gap=3 → sort, gap=1 → final sorted
Quick Sort
• Divide & Conquer
• Choose pivot → Partition → Recursively sort
• Example: [10,80,30,90], Pivot=30 → Partition
→ Sorted
Merge Sort
• Divide → Sort subarrays → Merge
• Example: [38,27,43,3]
• Divide → [38,27]+[43,3] → Merge →
[3,27,38,43]
Heap Sort
• Build max-heap → Extract elements → Sort
• Example: [4,10,3,5,1] → Heap → [1,3,4,5,10]
Sorting in Linear Time (Counting
Sort)
• Array = [4,2,2,8,3,3,1]
• Frequency Table → Sorted = [1,2,2,3,3,4,8]
Summary
• • Algorithm basics & flowchart
• • Time & space complexity
• • Growth of functions
• • Sorting techniques with examples