Scribd
Upload
3 views1 page

Algorithm CAT Report

The document outlines the design and analysis of algorithms, specifically Merge Sort and Binary Search, providing pseudocode for both. Merge Sort has a time complexity of O(n log n) and is efficient for large datasets, while Binary Search offers O(log n) lookup time for sorted data. Performance evaluations indicate that Merge Sort's runtime increases with larger inputs, whereas Binary Search remains nearly constant.

Uploaded by

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

Algorithm CAT Report

The document outlines the design and analysis of algorithms, specifically Merge Sort and Binary Search, providing pseudocode for both. Merge Sort has a time complexity of O(n log n) and is efficient for large datasets, while Binary Search offers O(log n) lookup time for sorted data. Performance evaluations indicate that Merge Sort's runtime increases with larger inputs, whereas Binary Search remains nearly constant.

Uploaded by

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

BSD 222: Design and Analysis of Algorithms

Project-Based CAT Report

1. Algorithm Design

Pseudocode for Merge Sort:


MERGE-SORT(A)
if length(A) ≤ 1 return A
mid ← floor(length(A)/2)
left ← MERGE-SORT(A[0:mid])
right ← MERGE-SORT(A[mid:])
return MERGE(left,right)

MERGE(left,right)
i ← 0; j ← 0
result ← empty list
while i < len(left) and j < len(right)
if left[i] ≤ right[j] append left[i]; i++
else append right[j]; j++
append remaining elements
return result

Pseudocode for Binary Search:


BINARY-SEARCH(A,target)
low ← 0; high ← len(A)-1
while low ≤ high
mid ← (low+high)//2
if A[mid] == target return mid
else if A[mid] < target low = mid+1
else high = mid-1
return -1

Justification:
Merge Sort guarantees O(n log n) performance for all cases, making it ideal for large delivery datasets.
Binary Search provides O(log n) lookup time, enabling fast parcel searches once data is sorted.

2. Implementation (Python)
(Include code snippets and screenshots in your final PDF submission.)

3. Time & Space Complexity


Merge Sort: Best/Average/Worst = O(n log n); Space = O(n)
Binary Search: Best = O(1), Avg/Worst = O(log n); Space = O(1) iterative

4. Performance Evaluation
Small input (10 items): extremely fast runtime.
Large input (1000 items): merge sort time increases following n log n growth; binary search time stays
nearly constant.

You might also like