Formula Sheets: Searching & Sorting | Algorithms - Computer Science Engineering (CSE) PDF Download

 Page 1


Searc hing and Sorting F orm ula Sheet
Searc hing Algorithms
• Linear Searc h :
– Time Complexit y: O(n) , where n is arra y size.
– Best Case: O(1) (elemen t at first p osition).
– A v erage Case: T
a vg
=
n+1
2
comparisons.
– Space Complexit y: O(1) .
• Binary Searc h (Iterativ e/Recursiv e) :
– Precondition: Arra y m ust b e sorted.
– Time Complexit y: O(logn) , where n is arra y size.
– Recurrence Relation: T(n) = T
(
n
2
)
+O(1) , solv es to T(n) = O(logn) .
– Num b er of Comparisons: ?log
2
(n+1)? .
– Space Complexit y: O(1) (iterativ e), O(logn) (recursiv e due to call stac k).
Sorting Algorithms Ov erview
• Comparison-Based Sorting : Lo w er b ound ?(nlogn) for a v erage case.
• Stabilit y : Stable if relativ e order of equal elemen ts is preserv ed.
• In-Place : Requires O(1) extra space (excluding recursion stac k).
Selection Sort
• Time Complexit y: O(n
2
) , where n is arra y s ize.
• Comparisons:
n(n-1)
2
.
• Sw aps: O(n) in w orst case.
• Space Complexit y: O(1) (in-place).
• Stabilit y: Not stable.
Insertion Sort
• Time Complexit y:
– W orst/A v erage: O(n
2
) .
– Best Case: O(n) (nearly sorted arra y).
• Comparisons:
n(n-1)
4
(a v erage).
• Shifts: O(n
2
) in w orst case.
• Space Complexit y: O(1) (in-place).
• Stabilit y: Stable.
Merge Sort
• Time Complexit y: O(nlogn) for all cases.
• Recurrence Relation: T(n) = 2T
(
n
2
)
+O(n) , solv es to T(n) = O(nlogn) .
• Space Complexit y: O(n) (auxiliary arra y for merging).
• Merge Op erations: O(n) p er lev el, logn lev els.
• Stabilit y: Stable.
• T w o-W a y Merge (Iterativ e): T
iterativ e
=O(nlogn) , space O(n) .
1
Page 2


Searc hing and Sorting F orm ula Sheet
Searc hing Algorithms
• Linear Searc h :
– Time Complexit y: O(n) , where n is arra y size.
– Best Case: O(1) (elemen t at first p osition).
– A v erage Case: T
a vg
=
n+1
2
comparisons.
– Space Complexit y: O(1) .
• Binary Searc h (Iterativ e/Recursiv e) :
– Precondition: Arra y m ust b e sorted.
– Time Complexit y: O(logn) , where n is arra y size.
– Recurrence Relation: T(n) = T
(
n
2
)
+O(1) , solv es to T(n) = O(logn) .
– Num b er of Comparisons: ?log
2
(n+1)? .
– Space Complexit y: O(1) (iterativ e), O(logn) (recursiv e due to call stac k).
Sorting Algorithms Ov erview
• Comparison-Based Sorting : Lo w er b ound ?(nlogn) for a v erage case.
• Stabilit y : Stable if relativ e order of equal elemen ts is preserv ed.
• In-Place : Requires O(1) extra space (excluding recursion stac k).
Selection Sort
• Time Complexit y: O(n
2
) , where n is arra y s ize.
• Comparisons:
n(n-1)
2
.
• Sw aps: O(n) in w orst case.
• Space Complexit y: O(1) (in-place).
• Stabilit y: Not stable.
Insertion Sort
• Time Complexit y:
– W orst/A v erage: O(n
2
) .
– Best Case: O(n) (nearly sorted arra y).
• Comparisons:
n(n-1)
4
(a v erage).
• Shifts: O(n
2
) in w orst case.
• Space Complexit y: O(1) (in-place).
• Stabilit y: Stable.
Merge Sort
• Time Complexit y: O(nlogn) for all cases.
• Recurrence Relation: T(n) = 2T
(
n
2
)
+O(n) , solv es to T(n) = O(nlogn) .
• Space Complexit y: O(n) (auxiliary arra y for merging).
• Merge Op erations: O(n) p er lev el, logn lev els.
• Stabilit y: Stable.
• T w o-W a y Merge (Iterativ e): T
iterativ e
=O(nlogn) , space O(n) .
1
Quic k Sort
• Time Complexit y:
– W orst Case: O(n
2
) (e.g., sorted arra y , piv ot is min/max).
– A v erage/Best Case: O(nlogn) .
• Recurrence Relation (A v erage): T(n) = 2T
(
n
2
)
+O(n) , solv es to T(n) = O(nlogn) .
• W orst Case Recurrence: T(n) = T(n-1)+O(n) , solv es to T(n) = O(n
2
) .
• Piv ot Selection: Median-of-three reduces w orst case probabilit y .
• Comparisons: 2nlnn˜ 1.386nlogn (a v erage).
• Space Complexit y: O(logn) (recursiv e call stac k), O(1) auxiliary (in-place).
• Stabilit y: Not stable.
Heap Sort
• Time Complexit y: O(nlogn) for all cases.
• Heapify Time: O(logn) p er elemen t, O(n) for heap c onstruction.
• Recurrence for Heapify: T(h) = 2T
(
h
2
)
+O(1) , where h is heap heigh t, solv es to O(logn) .
• T otal Op erations: O(n) for build-heap, O(nlogn) for extract-max/min.
• Space Complexit y: O(1) (in-place).
• Stabilit y: Not stable.
• Heap Heigh t: h =?logn? .
P erformance Metrics
• Time Complexit y Comparison :
– Linear Searc h: O(n) , Binary Searc h: O(logn) .
– Selection/Insertion: O(n
2
) , Merge/Quic k/Heap: O(nlogn) .
• Space Complexit y :
– In-Place: Selection, Insertion, Heap, Quic k (O(logn) stac k).
– Non-In-Place: Merge (O(n) ).
• A v erage Comparisons :
– Binary Searc h: logn .
– Quic k Sort: 1.386nlogn .
– Merge Sort: nlogn .
• Stabilit y Impact : Stable sorts (Merge, Insertion) preferred for main taining order of equal ele-
men ts.
• A daptiv e Sorting : Insertion Sort e?icien t for n= 10 or nearly sorted arra ys.
2