Scribd
Upload
35 views2 pages

Algorithm Analysis With Examples

The document analyzes the time complexity of three algorithms: Linear Search, Binary Search, and Insertion Sort, detailing their best, average, and worst case scenarios. Linear Search has a best case of O(1) and worst case of O(n), while Binary Search requires a sorted array and has a best case of O(1) and worst case of O(log n). Insertion Sort has a best case of O(n) when the array is sorted and a worst case of O(n²) when sorted in reverse order.

Uploaded by

BINDUANN THOMAS
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
35 views2 pages

Algorithm Analysis With Examples

The document analyzes the time complexity of three algorithms: Linear Search, Binary Search, and Insertion Sort, detailing their best, average, and worst case scenarios. Linear Search has a best case of O(1) and worst case of O(n), while Binary Search requires a sorted array and has a best case of O(1) and worst case of O(log n). Insertion Sort has a best case of O(n) when the array is sorted and a worst case of O(n²) when sorted in reverse order.

Uploaded by

BINDUANN THOMAS
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Best Case, Average Case, and Worst Case Analysis for Algorithms

---

1. Linear Search
Case Time Complexity Explanation

Best Case O(1) The element is found at the


first position.

Average Case O(n) The element is somewhere


in the middle (on average,
n/2 steps).

Worst Case O(n) The element is at the last


position or not present at all
(all n elements checked).

Example:

 - Array = [5, 10, 15, 20, 25]


 - Search for 5 (Best Case) - found at index 0.
 - Search for 20 (Average Case) - found after checking 3 elements.
 - Search for 30 (Worst Case) - element not found after checking all 5 elements.

---

2. Binary Search
(Requires a sorted array)

Case Time Complexity Explanation

Best Case O(1) The element is found at the


middle position on the first
comparison.

Average Case O(log n) Repeatedly dividing the


search space by 2.

Worst Case O(log n) Search space reduces to 1


element after log₂(n)
divisions.

Example:

 - Sorted Array = [5, 10, 15, 20, 25, 30, 35]


 - Search for 20 (Best Case) - middle element.
 - Search for 5 or 35 (Worst Case) - several divisions needed.

---

3. Insertion Sort
Case Time Complexity Explanation

Best Case O(n) The array is already sorted,


so only one comparison per
element.

Average Case O(n²) Elements are randomly


ordered; on average, half of
the previous elements need
to be compared.

Worst Case O(n²) The array is sorted in


reverse order; every new
element has to be compared
with all previous elements.

Example:

 - Best Case: [1, 2, 3, 4, 5] (Already sorted)


 - Average Case: [3, 1, 4, 5, 2]
 - Worst Case: [5, 4, 3, 2, 1] (Reverse order)

---

Summary Table
Algorithm Best Case Average Case Worst Case

Linear Search O(1) O(n) O(n)

Binary Search O(1) O(log n) O(log n)

Insertion Sort O(n) O(n²) O(n²)

---

You might also like