MIT OCW - Lecture 1(Analysis of Algorithms,Insertion Sort,Merge Sort)

I took the first lecture on Introduction to Algorithms from MIT Open CourseWare today morning. I had already completed two lectures one on Introduction to Algorithms and the second on Stacks from National Programme on Technology Enhanced Learning of India's youtube channel

I just wanted to compare between the two before deciding which one I would take fully.I think I will go with the MIT's lectures because

• I found the explanation of how the algorithms work more insightful on the MIT Lectures.
• The IIT lectures uses power point slides whereas the MIT guy uses a black board and writes it out during the class, I liked the second approach better because it gives time for the students to think and black board is so free form that it is easy to explain much better using it
• There are already lecture notes people have taken and posted on their blogs which I can refer to
• MIT Lectures seemed to have more stress on Math (which is hard for me but good for me)
• I already have the book the MIT course recommends to use for this course
  

But since the lecture will be using a black board, I think it is better to use a pen and paper than notepad for the notes.So I will not be posting the notes on the blog, I'll still put the code I do on my github repo.

Today I tried to capture some of the lecture at least using my notepad and here it is
Define Algorithm Analysis
Talked about things in a software program more important than performance
Insertion Sort Algorithm
The Running time of Algorithm depends on
a. type of input (whether fully sorted or partially sorted)
b. size of input
c. want upper bounds of time taken most of the time

Kinds of analysis
Worst case(usually)
T(n) = max time on any input of size n
Average case(sometimes)
T(n) = expected time over all inputs of size n
expected time is time for every input multiplied by the probablility that the input will occur,
hence for this we need the statistical distribution of inputs (for example all inputs are equally likely)
Best Case(bogus)
you can cheat by showing a slow algorithm as good over some input where on vast majority of inputs it is probably very bad

What is insertion sorts running time
Depends on computer
-relative speed ( compare two algorithms on same machine)
-Abolute speed ( compare two algorithms on different machine)

Asymptotic Analysis
a.Ignore Machine dependent constants
b.Look at the growth of the running time with respect to input (instead of looking at the actual running time)

Asymptotic notation
Theta notation - a. Drop lower order terms
b. Ignore leading constants

Analysis of Insertion Sort
Worst Case analysis
T(n) = Summation (j =2 to n) theta(j) = theta(n**2) (Arithemetic Series)

Merge Sort A[1..n]

1 if n = 1 , done , Time = Theta(1)
2 Recursively sort A[1, n/2] and A[(n/2)+1,n] Time =2*Theta(n/2)
3 Merge the two sorted lists = Time = Theta(n)

Merge sort time
if n = 1 (array is already sorted) , T(n) = Theta(1)
if n > 1 , T(N) = 2*Theta(n/2) + Theta (n)

Merge sort - Theta(nlogn) - The analysis was done graphically on blackboard