Introduction

Summary Three times

keywords algorithm analysis, growth of functions, asymptotic notation, big-O, omega, theta functions

TODO #todo : see through book and find 3 more sorting algorithms and learn. They are not popular because they use high space complexity

HW

Exercise* $\Omega(n)$ Draw the function stack steps.

Next time

Recap

caution In merge sort, we are not talking about parallel programming. It's a sequential excecution. Each function call is stacked in function call stack, paused when calling a smaller recursive functions.

We can implement mergesort with less memory usage. Try not to copy the array and pass (or sort).

Algorithm Analysis

(The book is analyzing algorithm one by one, each after introducing the algorithm)

Goal

We should be able to tell the time complexity just by seeing the code.

How do you analyze algorithm?

Check runtime (experimental approach)
- Why do we not do experimental approach?
- It is dependant to the experimenting infrastructure(data, machine, language..)
- Some algorithms is executed in so small time.
- Cannot test on small parts of a big code. should excecute the whole code.
compute the time complexity (theoretical approach)

Asymptotic Analysis

We count the number of primitive operations.

We are only interested in the pattern of growth of runtime when input grows.
Thus we only consider of the dominant terms (namely, that of highest order).

We use notation as a function of input (ex. $f(n)$)

There are three types

$O(n)$ :
$\Omega(n)$ :
$\Theta(n)$ : tight bond

#todo : fill out three functions

Big-O notation

The maximal runtime growth.

Constant $O(1)$
Logarithmic $O(log;n)$
linear $O(n)$
nlogn $O(n;log(n))$
Quadratic $O(n^2)$
exponential $O(a^n)$
factorial $O(n!)$

Usually The stage can be downgraded (more efficiently)

How to calculate

There are cost ( $c$ )of the operation, and the count ( $t$ ) of operation count each iterations, and check the highest order term.

Caution

include the loop index refreshing statements, and loop checking statements

Examples

Example 1 은 $O(n^2)$?
Example 2 은 $O(n^2)$?
Example 3 는 $p$<$n$ 이기 때문에 $ O( \sqrt n )$
Example 4 는 $O(\log_2 n)$
Example 5 는 $O(\log_2 n)$
Example 6 $O(n)$

p=0
for (int i=0<i<n;i=i*2) {
	p++;
}
for(int j=0;j<p;j=j*2) {
	statement;
}

2nd loop in code above has time complexity of $O(\log p)$. So, the code is $O(\log n + \log \log n)$ -> $O(\log n)$

p=0;
for (int i=0; i<n;i++) {
	for(int j=1;j<n;j*2) {
		stmt;
	}
}

The code is $O(n \log n)$

for (int i=0;i<n;i++) {
	stmt;
}

for (int j=o;j<k;j++) {
	stmt;
}

The code is $O(n+k)$

#todo : do the examples of calculating big-O of several codes.

Other Asysmptotic notations

Theta : tight bound
Big -O : Upper bound
Omega : Lower Bound

Introduction

Recap

Algorithm Analysis

Goal​

How do you analyze algorithm?​