Recap

Functions and Running time

Digression towards Sorting
The link between algorithms and functions

In the previous lecture we tried to look into the basics of asymptotic

notations and how they can be used to compare two functions.

In pursuit of understanding the growth of functions, we also looked

at
I Big Oh notation
I Omega notation
I Theta notation
I little oh and little omega notation
 Recap
Functions and Running time
Digression towards Sorting
The link between algorithms and functions

So right now we know that if we can associate a function with an

algorithm we can analyse if it is efficient or not.
 Recap
Functions and Running time
Digression towards Sorting
The link between algorithms and functions

So right now we know that if we can associate a function with an

algorithm we can analyse if it is efficient or not.

But how does one find a function associated with an algorithm.

Till this point, whenever we looked at algorithms/code, we saw
I input/output commands
I some loops (if, for, while) and
I some mathematical operations like addition or multiplication.
 Recap
Functions and Running time
Digression towards Sorting
The link between algorithms and functions

So right now we know that if we can associate a function with an

algorithm we can analyse if it is efficient or not.

But how does one find a function associated with an algorithm.

Till this point, whenever we looked at algorithms/code, we saw
I input/output commands
I some loops (if, for, while) and
I some mathematical operations like addition or multiplication.

How do these simple operations translate into functions? Before we

answer this question, lets digress and take a look at something
simple.
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

Imagine that you are newly appointed as a librarian.

If the library has placed the books in an arbitrary order, then you
may have to look at the entire catalogue to find the book you are
looking for.
In the worst case, you may end up looking at the cover of each book
and realize that the book you are looking for is not present in the
library.

So keeping the books in a sorted order helps to retrieve a book.

 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

Books can be sorted either

I Categorically and then alphabetically or
I Based on their ISSN (8 digit number).
You think that sorting them according to category may not be
useful, because a book may fall into several categories.

Sorting them according to the first alphabet of the title may also
not be useful, because lots of books start with the word “ The ”.

Since dealing with integers is easier for computers you try to sort
them based on the ISSN of each book.
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

Librarian(to himself):- How will I sort so many books at the same

time. I must develop an algorithm.

Before I deal with 10K books let me try sorting just 10 books.
Sorting ten books is like having a hand of cards in sorted order.
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

Librarian(to himself):- How will I sort so many books at the same

time. I must develop an algorithm.

Before I deal with 10K books let me try sorting just 10 books.
Sorting ten books is like having a hand of cards in sorted order.

Eureka moment:- Solving a smaller instance of problem gives

insight towards dealing with a larger instance of that
problem.
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

It is easy to sort the 10 books by simple brute force. But then how
does it help me in sorting 10K books?
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

It is easy to sort the 10 books by simple brute force. But then how
does it help me in sorting 10K books?

If I can sort 11 books using this strategy, then maybe I can extend
that strategy to sort 10K books.

Sorting 11 books is easy, if you already have 10 books in sorted

order and only one book is possibly out of order. Simply compare
ISSN of the 11th book (with the ISSN of the 10 books) to find its
correct location.
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

It is easy to sort the 10 books by simple brute force. But then how
does it help me in sorting 10K books?

If I can sort 11 books using this strategy, then maybe I can extend
that strategy to sort 10K books.

Sorting 11 books is easy, if you already have 10 books in sorted

order and only one book is possibly out of order. Simply compare
ISSN of the 11th book (with the ISSN of the 10 books) to find its
correct location.

Eureka Moment:- If I have a partially sorted solution for k

books, I can easily insert a new book in its correct location
and build a solution of k + 1 sorted books using k
comparisons.
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

Strategy/Pseudocode

While(# Books which are out of order is non-zero)

{
If the sorted pile is not empty then
Take a book from the unsorted pile and insert in the Sorted pile
at its correct location.
Otherwise
Place an arbitrary book in the sorted pile from the unsorted pile.
}
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

Sanity Check

Since we are always inserting a new book in the sorted list of books,
we shall call it insertion sorting algorithm.

Its easy to confirm that this algorithm terminates in a finite amount

of time and that it correctly outputs the correct sorted list of books
based on their ISSN.

Now, we have the task of transforming this real world

problem/algorithm into something which a computer can
understand.
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

We take the list of all ISSN in an array of size 10K.

This array shall consist of two parts.

I One contiguous part consists of sorted ISSN followed by
I An adjacent contiguous part consisting of unsorted ISSN.

Initially all the ISSN are unsorted.

 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

Pseudocode for Machine/Coding

Let A be the array of size 10K. We assume a zero-based array, so the

first element in the array is A[0] and the last element is A[10K − 1].

for(i : 1 to length(A) − 1)
{
j = i;
while(j > 0 and A[j − 1] > A[j])
{
swap A[j] and A[j − 1];
j = j − 1;
}
}
 Why sort?
Recap Observations
Functions and Running time Heuristic
Digression towards Sorting Pseudocode for layman
The link between algorithms and functions Correctness
Pseudocode for Computers

The “for” loop executes till it scans the entire array.

The “while” loop is executed everytime a new element from the

unsorted part is found to be smaller than the last element of the
sorted part.

This “while” loop puts the newly added element at its right location
in the sorted part of the array, by swapping elements till the newly
added element finds its right location.
 Recap
Algorithms to recurrences
Functions and Running time
Recurrences to functions
Digression towards Sorting
Solving Recurrences by Guessing
The link between algorithms and functions

Now we come back to the question we started with.

“How to associate an algorithm with a function?”
 Recap
Algorithms to recurrences
Functions and Running time
Recurrences to functions
Digression towards Sorting
Solving Recurrences by Guessing
The link between algorithms and functions

Now we come back to the question we started with.

“How to associate an algorithm with a function?”

We shall recollect the important observations:-

1. If we have a list of n − 1 sorted elements, then we need to
compare the new element with the remaining n − 1 sorted
elements to create a sorted list of n elements.
2. If we have a list of 2 elements, then we need just one
comparison to sort the list.
 Recap
Algorithms to recurrences
Functions and Running time
Recurrences to functions
Digression towards Sorting
Solving Recurrences by Guessing
The link between algorithms and functions

Let T (n) denote the number of comparisons (aka basic operations)

which are sufficient to sort an input of size n.
From our observation we can write that

T (n) = T (n − 1) + n − 1
T (2) = 1

This has helped us to associate a recurrence relation. Now we need

to know how to solve a recurrence relation.
 Recap
Algorithms to recurrences
Functions and Running time
Recurrences to functions
Digression towards Sorting
Solving Recurrences by Guessing
The link between algorithms and functions

If we solve the recurrence, then we will have the running time of the
algorithm.

This running time will be the worst case running time.

No matter what input permutation is given, the insertion sort

algorithm will not take more than T (n) number of comparisons to
sort the list of n elements.
 Recap
Algorithms to recurrences
Functions and Running time
Recurrences to functions
Digression towards Sorting
Solving Recurrences by Guessing
The link between algorithms and functions

In this case we try to guess the value of T (n) for small values of n
and see how it helps.

T (3) = T (2) + 2 = 1 + 2 = 3
T (4) = T (3) + 3 = 6
T (5) = T (4) + 4 = 10

In general, it seems that

n−1
X (n − 1)n
T (n) = i=
2
i=1

which one can easily prove using induction. Thus T (n) = O(n2 ).
 Recap
Algorithms to recurrences
Functions and Running time
Recurrences to functions
Digression towards Sorting
Solving Recurrences by Guessing
The link between algorithms and functions

Although, with experience one can look at a recurrence and have a

rough guess about its running time, it is not wise to depend on
guess work to solve recurrences.

In the next lecture we will look at general methods used for solving
recurrences.
 Recap
Algorithms to recurrences
Functions and Running time
Recurrences to functions
Digression towards Sorting
Solving Recurrences by Guessing
The link between algorithms and functions

Additional materials to look at

I Read about selection sort
I Websites to help visualize insertion sorting
I https://visualgo.net/bn/sorting
I (2 min video)
https://www.youtube.com/watch?v=JU767SDMDvA
I Understanding the duality between insertion and selection sort.
https://www.youtube.com/watch?v=pcJHkWwjNl4