FDS Lecture 1

Chapter 1 & 2

is known as HARMONIC NUMBERS, the sum is called HARMONIC SUM.

ERROR in the approximate is called EULER’S CONSTANT( = 0.57732566**)**

A is congruent to B modulo N can be written as:

---

Proving by INDUCTION or CONTRADICTION or COUNTEREXAMPLE

---

Brief of Recursion

1. Base cases. You must always have some base cases, which can be solved
   without recursion
2. Making progress. For the cases that are to be solved recursively, the recursive
   call must always be to a case that makes progress toward a base case.
3. Design rule. Assume that all the recursive calls work
4. Compound interest rule. Never duplicate work by solving the same instance of a problem in separate recursive calls

---

Algorithm Analysis

IMPORTANT MATH NOTATIONS!

1. Big-Oh Notation

   if there are positive constant and such that when

2. Omega Notation

   if there are positive constant and such that when

3. Theta Notation

   if and only if and

4. Little-Oh Notation

   if and

   To establish a relative order among functions

   • Big-Oh - Growth rate is less or equal to
   • Omega - Growth rate is larger or equal to
   • Theta - Growth rate is equal to
   • Little-Oh - Growth rate is less than

Determination of

How to determine the growth rate of and ?

Calculate:

• The limit is 0: This means that .
• The limit is : This means that .
• The limit is : This means that .
• The limit oscillates: There is no relation.

Whenever possible, algorithms be efficient enough not to be the bottleneck of a problem

---

Rules for Algorithm Analysis

R1—FOR LOOPS:

The running time of a for loop is at most the running time of the statements inside the for loop (including tests) times the number of iterations.

R2—NESTED FOR LOOPS:

Analyze these inside out. The total running time of a statement inside a group of nested loops is the running time of the statement multiplied by the product of the sizes of all the for loops

R3—CONSECUTIVE SATEMENTS:

These just add.

R4 - IF/ELSE

For the fragment

if(Condition)
    S1
else
    S2

the running time of an if/else statement is never more than the running time of the test plus the larger of the running times of S1 and S2

---

If and ,

Then

Ways to Calculate the Time Complexity

• Declaration counts for NO TIME
• Initializing, judgement, operation counts
• NO NEED to take all the statement into acount

Fibbonaci

int Fib(int N){
	if(N<=1) return 1;
	else return Fib(N-1) + Fib(N-2)
}

From we can know that (Here 2 counts for the returning of the number and adding them togther)

Therefore, Fib(N)> , which means that calculating Fibbonaci recursively grows potentially. Not a good way to calc.