Algorithm Analysis

Submitted By:-Ms.Mehak Kapoor

PG DEPT COMPUTER SCIENCE &IT

1

What is an algorithm?

• An algorithm is “a finite set of precise instructions for performing a computation or for solving a problem”
• A program is one type of algorithm
• All programs are algorithms
• Not all algorithms are programs!
• Directions to somebody’s house is an algorithm
• A recipe for cooking a cake is an algorithm
• The steps to compute the cosine of 90° is an algorithm

2

Some algorithms are harder than others

• Some algorithms are easy
• Finding the largest (or smallest) value in a list
• Finding a specific value in a list
• Some algorithms are a bit harder
• Sorting a list
• Some algorithms are very hard
• Finding the shortest path between Miami and Seattle
• Some algorithms are essentially impossible
• Factoring large composite numbers

​

• In section 2.2, we’ll see how to rate how “hard” algorithms are

3

Algorithm 1: Maximum element

• Given a list, how do we find the maximum element in the list?

​

• To express the algorithm, we’ll use pseudocode
• Pseudocode is kinda like a programming language, but not really

4

Algorithm 1: Maximum element

• Algorithm for finding the maximum element in a list:

​

procedure max (a₁, a₂, …, a_n: integers)

max := a₁

for i := 2 to n

if max < a_i then max := a_i

​

{max is the largest element}

​

5

Algorithm 1: Maximum element

procedure max (a₁, a₂, …, a_n: integers)

max := a₁

for i := 2 to n

if max < a_i then max := a_i

6

max := a₁

for i := 2 to n

if max < a_i then max := a_i

2

3

4

5

6

7

8

9

10

4

7

9

Maximum element running time

• How long does this take?

​

• If the list has n elements, worst case scenario is that it takes n “steps”
• Here, a step is considered a single step through the list

7

Properties of algorithms

• Algorithms generally share a set of properties:
• Input: what the algorithm takes in as input
• Output: what the algorithm produces as output
• Definiteness: the steps are defined precisely
• Correctness: should produce the correct output
• Finiteness: the steps required should be finite
• Effectiveness: each step must be able to be performed in a finite amount of time
• Generality: the algorithm should be applicable to all problems of a similar form

8

Searching algorithms

• Given a list, find a specific element in the list

​

• We will see two types
• Linear search
• a.k.a. sequential search
• Binary search

9

Algorithm 2: Linear search

• Given a list, find a specific element in the list
• List does NOT have to be sorted!

​

procedure linear_search (x: integer; a₁, a₂, …, a_n: integers)

i := 1

while ( i ≤ n and x ≠ a_i )

i := i + 1

if i ≤ n then location := i

else location := 0

​

{location is the subscript of the term that equals x, or it is 0 if x is not found}

10

Algorithm 2: Linear search, take 1

11

procedure linear_search (x: integer; a₁, a₂, …, a_n: integers)

i := 1

while ( i ≤ n and x ≠ a_i )

i := i + 1

if i ≤ n then location := i

else location := 0

i := 1

while ( i ≤ n and x ≠ a_i )

i := i + 1

if i ≤ n then location := i

else location := 0

2

3

4

5

6

7

8

1

Algorithm 2: Linear search, take 2

12

procedure linear_search (x: integer; a₁, a₂, …, a_n: integers)

i := 1

while ( i ≤ n and x ≠ a_i )

i := i + 1

if i ≤ n then location := i

else location := 0

i := 1

while ( i ≤ n and x ≠ a_i )

i := i + 1

if i ≤ n then location := i

else location := 0

2

3

4

5

6

7

8

9

10

1

11

Linear search running time

• How long does this take?

​

• If the list has n elements, worst case scenario is that it takes n “steps”
• Here, a step is considered a single step through the list

13

Algorithm 3: Binary search

• Given a list, find a specific element in the list
• List MUST be sorted!
• Each time it iterates through, it cuts the list in half

​

procedure binary_search (x: integer; a₁, a₂, …, a_n: increasing integers)

i := 1 { i is left endpoint of search interval }

j := n { j is right endpoint of search interval }

while i < j

begin

m := ⎣(i+j)/2⎦ { m is the point in the middle }

if x > a_m then i := m+1

else j := m

end

if x = a_i then location := i

else location := 0

​

{location is the subscript of the term that equals x, or it is 0 if x is not found}

14

Algorithm 3: Binary search, take 1

15

i := 1

j := n

while i < j

begin

m := ⎣(i+j)/2⎦

if x > a_m then i := m+1

else j := m

end

if x = a_i then location := i

I

m

j

Algorithm 3: Binary search, take 2

16

i := 1

j := n

while i < j

begin

m := ⎣(i+j)/2⎦

if x > a_m then i := m+1

else j := m

end

if x = a_i then location := I

else location := 0

1

10

5

6

8

8

7

8

Algorithm 3: Binary search

• A somewhat alternative view of what a binary search does…

17

Binary search running time

• How long does this take (worst case)?

​

• If the list has 8 elements
• It takes 3 steps
• If the list has 16 elements
• It takes 4 steps
• If the list has 64 elements
• It takes 6 steps

​

• If the list has n elements
• It takes log₂ n steps

18

Sorting algorithms

• Given a list, put it into some order
• Numerical, lexicographic, etc.

​

• We will see two types
• Bubble sort
• Insertion sort

19

Algorithm 4: Bubble sort

• One of the most simple sorting algorithms
• Also one of the least efficient
• It takes successive elements and “bubbles” them up the list

​

procedure bubble_sort (a₁, a₂, …, a_n)

for i := 1 to n-1

for j := 1 to n-i

if a_j > a_j+1

then interchange a_j and a_j+1

{ a₁, …, a_n are in increasing order }

20

Algorithm 4: Bubble sort

21

for i := 1 to n-1

for j := 1 to n-i

if a_j > a_j+1

then interchange a_j and a_j+1

Bubble sort running time

• Bubble sort algorithm:

for i := 1 to n-1

for j := 1 to n-i

if a_j > a_j+1

then interchange a_j and a_j+1

​

• Outer for loop does n-1 iterations
• Inner for loop does
• n-1 iterations the first time
• n-2 iterations the second time
• …
• 1 iteration the last time
• Total: (n-1) + (n-2) + (n-3) + … + 2 + 1 = (n²-n)/2
• We can say that’s “about” n² time

22

Algorithm 5: Insertion sort

• Another simple (and inefficient) algorithm
• It starts with a list with one element, and inserts new elements into their proper place in the sorted part of the list

​

procedure insertion_sort (a₁, a₂, …, a_n)

for j := 2 to n

begin

i := 1

while a_j > a_i

i := i +1

m := a_j

for k := 0 to j-i-1

a_j-k := a_j-k-1

a_i := m

end { a₁, a₂, …, a_n are sorted }

23

take successive elements in the list

find where that element should be in the sorted portion of the list

move all elements in the sorted portion of the list that are greater than the current element up by one

put the current element into it’s proper place in the sorted portion of the list

Insertion sort running time

for j := 2 to n begin

i := 1

while a_j > a_i

i := i +1

m := a_j

for k := 0 to j-i-1

a_j-k := a_j-k-1

a_i := m

end { a₁, a₂, …, a_n are sorted }

• Outer for loop runs n-1 times
• In the inner for loop:
• Worst case is when the while keeps i at 1, and the for loop runs lots of times
• If i is 1, the inner for loop runs 1 time (k goes from 0 to 0) on the first iteration, 1 time on the second, up to n-2 times on the last iteration
• Total is 1 + 2 + … + n-2 = (n-1)(n-2)/2
• We can say that’s “about” n² time

24

Comparison of running times

• Searches
• Linear: n steps
• Binary: log₂ n steps
• Binary search is about as fast as you can get

​

• Sorts
• Bubble: n² steps
• Insertion: n² steps
• There are other, more efficient, sorting techniques
• In principle, the fastest are heap sort, quick sort, and merge sort
• These each take take n * log₂ n steps
• In practice, quick sort is the fastest, followed by merge sort

25

​

​

​

THANK YOU!

26