Skip to main content

Introduction

Summary Should know the definition of each aymptotic notations. Important chapter for midterm.

keywords

TODO

  • #todo: paste some images for better understanding.
  • #todo : look for the substitution method is the textbook.

HW

Exercise*

Next time growth function, Recursion, substitution method.

Recap

Algorithm Analysis, time complexity, asymptotic notations

Asymptotic Notations

  • It should follow the similar pattern of the runtime growth.
  • how to find? substitution method. Change all the #todo : look more for the substitution method

Big- O​

  • Upper bound.
  • It should follow the similar pattern of the runtime growth.
  • $O(g(n))$ : there exists a $n_0$ ,positive constants $C$, such that in $n_0 < n$, the runtime $f(n)$ is bound over. $f(n) < c g(n)$

example. $f(n) = 2n+3$ in $f(n) = 2n+3$, the function is smaller than $5n$ in $n>=1$ so, $c=5$ , $g(n) =n$

Meanwhile, $g(n) = n^2, g(n)= n^3$ is also feasible. But generally we call it in the minimum order.

so, $f(n)$ is $O(n)$.

Big- Omega​

  • Lower bound.
  • $\Omega(g(n))$ : there exists a $n_0$ ,positive constants $C$, such that in $n_0 < n$, the runtime $g(n)$ is bound over. $f(n)$ < $= c g(n)$

example. $f(n) = 2n+3$ in $f(n) = 2n+3$, the function is bigger than $2n$ in $n>=1$ so, $c=2$, $g(n) = n$

Meanwhile, $g(n) = \log n;g(n)=1$ is alsow feasible. But generally we call it in the maximum order.

so, $f(n)$ is $\Omega (n)$.

Big- Theta​

  • Tight bound.
  • It should follow the similar pattern of the runtime growth.
  • there exists a $n_0$ ,positive constants $C_1,;C_2$, such that in $n_0 < n$, the runtime $g(n)$ is bound within $c_1 f(n)$ < $= g(n)$ < $= c_2 f(n)$

example. $f(n) = 2n+3$ in $f(n) = 2n+3$, the function is $2n$<$= 2n+3$<$=5n$ so, $c_1=2$, $C_2 = 5$, $g(n) = n$

  • The theta is when big omega and big O is the same.
  • There is only one representation function.

Caution There exist functions that can't be expressed with big-theta. Those functions have different big-$\Omega$ and big-O.

example : factorials $f(n) = n!$

example 2 : meaningful bound is hard to find. $f(n) = nn(n-1)(n-2)...(n)$ there is no meaningful minimum bound. only big-O is found, big-O is $O(n^n)$ .

small-o, small -omega They are strictly less or bigger. It is a bit tighter than that of their big notations.

Best-case, Worst Case

Caution. Big-O notation and Big-Omega notation has nothing to do with best&worst case. This is only a test scenario focused on the data itself. The notations is focused on the sequence of commands.

You express the best case and worst case in asymptotic notations. However, when you are asked for the time complexity of the algorithm, #todo : the confusion between best cases and time complexity

#todo : Minimum worst case? Maximum best case?

Example1 . linear Search

Best case : when the key is in the first position. Best case time : O(1)

Worst case : when the key is at the last position. Worst case time : O(n)

Average case : (All possible case time) / (# of cases) usually the worst case.

most times, we call the

Example2. Binary search

remark For some algorithms, Worst cases are two types minimum worst case : balanced tree data structure, first element $O(1)$?? maximum worst case : linear shaped tree data structure, end element $O(n)$??

#todo : recap on the two types of worst cases.

it happens for certain algorithms with specific algorithms