Scribd
Upload
7 views3 pages

DAA Algorithms Notes

The document provides notes on various algorithms including Linear Search, Binary Search, Bubble Sort, Selection Sort, Merge Sort, and Quick Sort. Each algorithm is defined along with its best and worst case time complexities and pseudocode. The notes highlight the efficiency of different sorting and searching techniques.

Uploaded by

maliktalha0442
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
7 views3 pages

DAA Algorithms Notes

The document provides notes on various algorithms including Linear Search, Binary Search, Bubble Sort, Selection Sort, Merge Sort, and Quick Sort. Each algorithm is defined along with its best and worst case time complexities and pseudocode. The notes highlight the efficiency of different sorting and searching techniques.

Uploaded by

maliktalha0442
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

Design and Analysis of Algorithms (DAA) Notes

1) Linear Search

Definition: Checks each element one by one until the key is found or list ends.

Best Case: O(1)

Worst Case: O(n)

Pseudocode:

for i = 0 to n-1

if A[i] == key return i

return -1

2) Binary Search

Definition: Works on sorted array and divides search space into half.

Best Case: O(1)

Worst Case: O(log n)

Pseudocode:

while low <= high

mid = (low+high)/2

if A[mid] == key return mid

3) Bubble Sort

Definition: Repeatedly swaps adjacent elements if in wrong order.

Best Case: O(n)

Worst Case: O(n^2)


Pseudocode:

for i = 0 to n-1

for j = 0 to n-i-2

if A[j] > A[j+1] swap

4) Selection Sort

Definition: Selects minimum element and places it at correct position.

Best Case: O(n^2)

Worst Case: O(n^2)

Pseudocode:

for i = 0 to n-1

find minimum element

swap with A[i]

5) Merge Sort

Definition: Divide and Conquer algorithm. Divides array, sorts and merges.

Best Case: O(n log n)

Worst Case: O(n log n)

Recurrence: T(n) = 2T(n/2) + O(n)

6) Quick Sort

Definition: Divide and Conquer algorithm using pivot partition.

Best Case: O(n log n)

Worst Case: O(n^2)

Recurrence: T(n) = T(k) + T(n-k-1) + O(n)

You might also like