DS5 ALGORITHM ANALYSIS

Question 1

MATHEMATICAL ANALYSIS OF ALGORITHMS

Answer 1

program exec time = instruction exec time * execution frequency

constant c(msec) for basic instructions ( c depends on the system)
example: loop
for(int i = 0; i <n; i++) a[i] = 5;
once i = 1
n + 1 loop condition
i++ n times
a[i] = 5 n times
so exec is c(n+n+n+1+1) = c(3n+2)
all other variables except c depend on the chosen algorithm so thats what the focus is on (what we can optimize as programmers)

mathematical analysis is precise and gives predictions but unnecessarily complex sometimes so we focus on scale
O() notation

Question 2

USEFUL NOTE FOR HOW FUNCTIONS INCREASE

Answer 2

1 < logn < n^1/2 < n < nlogn < n(logn)^2 < n(n)^1/2 < n^2 <n!
logn refers to base 2 since we are working in binary systems in cs

Question 3

BIG O NOTATION

Answer 3

we categorize algorithms based on their closest (that we can calculate) upper limit based on n inputs or n scale input
f(n) is O(g(n)) if for constant c f(n) <= c*g(n)
as long as c is a constant it is irrelevant to us how big it is
we just want to see how drastically the complexity increases as n increases

Question 4

SOME EXAMPLES

Answer 4

sequential search (sorted and unsorted array): O(n)
binary search (by definition sorted): O(logn)