# Week 1

- Grade School Multiplication Algorithm
- Karatsuba Multiplication Algorithm
- Sorting
- How does sorting work in case of all distinct elements?
- How does sorting work in case of repeating elements?
- How does sorting work in case of all same elements?
- Implement Merge-Sort, considering all these cases separately.

- Merge-sort
- How does Merge-Sort implementation differ in case of repeating elements?
- Merge-sort running time complexity? = 6n * (log n + 1)
- Height of recursion tree= log(2) n +1

- y=log(n) is always less than y=n
- Implementations= Merge-Sort, Basic Sorts, Karatsuba(if possible)
- Asymptotic Analysis
- Coarse enough to suppress implementation details, fine enough to differentiate different algorithms

- Big O Notation
- T(n)=O(F(n)) if and only if there exist constants c, n0 >0 such that

T(n)<=c*F(n) for all n>=n0

- T(n)=O(F(n)) if and only if there exist constants c, n0 >0 such that
- Big Omega Notation
- T(n)=Omega(F(n)) if and only if there exist constants c, n0 >0 such that

T(n)>=c*F(n) for all n>=n0

- T(n)=Omega(F(n)) if and only if there exist constants c, n0 >0 such that
- Big Theta Notation
- T(n)=Theta(F(n)) if and only if there exist constants c, n0 >0 such that

T(n)=O(n) and T(n)=Omega(n) for all n>=n0 - For all constants c1,c2, n0 such that c1F(n)<=T(n)<=c2F(n)

- T(n)=Theta(F(n)) if and only if there exist constants c, n0 >0 such that
- Little O Notation
- T(n)=O(F(n)) if and only if for all constants c>0, there exists a constant n0 such that T(n)<=c*F(n) for all n>=n0

## Principles for Design and Analysis of Algorithms

- Design algorithms for worst-case scenarios.
- Best fit for design sub-routines
- In case target function/field is known, we may consider average-case scenarios and benchmarks==Requires domain knowledge
- Worst case calculations are easier than average case calculations

- Constants are not important.
- Constants depend more on architecture/compiler/programmer
- Granularity achieved at this level is perfectly acceptable.

- Focus on Asymptotic Analysis
- Focus on running time for large input sizes

**Fast Algorithm===Worst case running time grows slowly for increasing input**

Advertisements