Scribd
Upload
13 views25 pages

AOA Lecture 7

The document provides an overview of algorithm analysis, focusing on performance metrics such as time and space complexity, and various sorting algorithms including insertion sort and selection sort. It discusses asymptotic notations like Big-O, Little o, and their implications for algorithm efficiency. Additionally, it highlights the characteristics and advantages of insertion sort compared to other sorting methods.

Uploaded by

aryavinodk83
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
13 views25 pages

AOA Lecture 7

The document provides an overview of algorithm analysis, focusing on performance metrics such as time and space complexity, and various sorting algorithms including insertion sort and selection sort. It discusses asymptotic notations like Big-O, Little o, and their implications for algorithm efficiency. Additionally, it highlights the characteristics and advantages of insertion sort compared to other sorting methods.

Uploaded by

aryavinodk83
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
You are on page 1/ 25

Analysis of Algorithms

CE – SE –SEM IV
Suneha Raut
SIES Graduate School of Technology

1
Overview
• Performance analysis , space complexity

• time complexity

• Growth of function – Big –Oh ,Omega , Theta notation

• Mathematical background for algorithm analysis

• Analysis of selection sort , insertion sort

• Recursive algorithms

• The substitution method

• Recursion tree method

3
Little oh

4
Little Omega

5
Asymptotic notation

6
• Thus, Little o means loose upper-bound of f(n). Little o is a rough
estimate of the maximum order of growth whereas Big-O may be the
actual order of growth.

•
7
8
9
10
Algorithm Analysis

1. Approach
2. characteristics …
3. Algorithm
4. Example (with iteration)
5. Time complexity for all cases and space complexity

11
Approach

• Insertion sort is a straightforward, efficient sorting algorithm,


particularly useful for small datasets.
• It works by building a sorted array one element at a time, picking
each element from the unsorted section and inserting it into its
correct position in the sorted part.

12
Analysis of Insertion Sort

13
14
15
16
Best case Analyasis

17
Worst case analysis

18
Worst case analysis

19
20
•Insertion sort is a straightforward sorting algorithm that constructs the
final sorted array (or list) one item at a time. On big lists, it is significantly
less efficient than more sophisticated algorithms such as quicksort,
heapsort, or merge sort. Insertion sort, on the other hand, has numerous
advantages:
•Easy to implement
•Like other quadratic sorting methods, it is effective for (relatively) small d
ata sets.
•In reality, it is more efficient than most other basic quadratic (i.e., O(n2))
algorithms like selection sort or bubble sort.
•Adaptive: Runs in near linear time for almost sorted array
•Stable: Relative order of identical elements does not alter even after
sorting
•In-place. Requires constant amount (O(1)) of additional space to sort the
given array.
•Online: It can sort the list as data arrives. Do no require the entire array to
be in memory while algorithm runs

21
Selection Sort

22
Properties of selection sort

• In place – O(1) Extra Space: Advantage over other algorithm


when auxiliary memory is limited
• Not Adaptive
• Not stable
• Can be implemented as a stable sort if, rather than swapping in
step 2, the minimum value is inserted into the first position (that
is, all intervening items moved down)
• It requires a data structure that supports efficient insertions ,
such as a linked list, or it leads to performing
• O(n2) writes.
• O(n2) Comparison
• O(n) Swap

23
References
• Ellis Horowitz, Sartaj Sahni, S. Rajsekaran. “Fundamentals of computer algorithms”
University Press.

24
•THANK YOU

25

You might also like