Recursive Algorithm

• A recursive procedure is a procedure that invokes itself.
• Recursion is a powerful and elegant way to solve problems, using divide and conquer technique.

  Decompose a problem into smaller problems of the same type as the original problem.

• ต้องมี Base Case ด้วย อย่าลืม!

Complexity of Algorithms (Big-O)

• “Complexity of an algorithm” refers to: “the amount of time and space required to execute the algorithm”.
• “Analysis of an algorithm” refers to: “the process of deriving estimates for the time and space needed to execute the algorithm”.
• The time needed to execute an algorithm is usually estimated as a function of the size of input.
• Given an algorithm, we can ask for:
  • The best-case time for inputs of size n
    • The minimal time needed to execute the algorithm among all inputs of size n.
  • The worst-case time for inputs of size n
    • The maximum time needed to execute the algorithm among all inputs of size n.
  • The average-case time for inputs of size n
    • The average time needed to execute the algorithm over some finite set of inputs all of size n.

• We could measure the time required by an algorithm by counting the number of instruction executed.
• Alternatively, we could use a cruder time estimate, such as the number of times each loop is executed.

Big-O

• Bigger and simple
  • คือ ทำยังไงให้ได้ให้ $g(n)$ มากกว่า $f(n)$ ส่วนใหญ่แล้วทำโดยการเอาพจน์ใหญ่ที่สุดไปแทน

Big-Omega ($\Omega$)

• Smaller and simple
  • คือทำยังไงก็ได้ให้ $g(n)$ น้อยกว่า $f(n)$ จะตัดพจน์หลังออกไปก็ได้ ส่วนใหญ่ทำแบบนั้น
  • Keep only the term with the highest degree

Big-Theta ($\Theta$)

• อันที่มีในทั้ง Big-O และ Big-Omega จะเรียกว่า “Big-Theta”
  • There’s only one Big-Theta notation

More Clever Approach (สำหรับ Big-$\ohm$)

• ถ้าทำอย่างที่บอกเช่น ตัดพจน์ หรือ เอาพจน์ที่ Degree มากสุดมาแทน บางครั้ง Big-O กับ Big-Omega is different → Deduce Big-Theta ไม่ได้ (เพราะ Big-Omega ต่ำไป)
• ดังนั้นเราจะมี Guideline for removing about a HALF of a sequence.
  • โดยที่เราจะ remove only about the first half
  • Guideline will work whether $n$ is odd or even.
  • First element to keep $\lceil{\frac{n}{2}}\rceil$
  • Number of remaining element $\lceil{\frac{n+1}{2}}\rceil$

Algorithm followed by another algorithm

• Long story short, conclude ได้เลยว่า $f_1(n)+f_2(n)=\Theta(g_{big}(n))$

Misconception

• $O$ — Order at most (upper bound) IS NOT $t_{worst}(n)$
• $\ohm$ — Order at least (lower bound) IS NOT $t_{best}(n)$
• $\Theta$ — Order (Estimate) IS NOT $t_{average}(n)$
• Each of $t_{best}(n), t_{average}(n), t_{worst}(n)$ can have their own $O, \ohm, \Theta$
  • The best-case, worst-case, and average-case complexities of an algorithm may each have different asymptotic bounds. For example, an algorithm may have different $O$, $\ohm$, and $\Theta$ for each of its best, worst, and average cases.

Complexity of Algorithms (in for-loop programming)

	\begin{algorithm}
	\caption{Find a theta notation in terms of $n$ for the number of times the statement $x := x + 1$ is executed.}
	\begin{algorithmic}
	\For{$i := 1$ \to $n$}
		\For{$j := 1$ \to $i$}
			\State $x:= x+1$
		\EndFor
	\EndFor
	\end{algorithmic}
	\end{algorithm}
	

• หลักการทำก็คือเขียนออกมาเลย ไล่ออกมาเป็น Linear Sum ง่าย ๆ แล้วค่อย Generalize ให้อยู่ใน Term ของ $n$ แล้วค่อยหา Theta notation ตามที่โจทย์สั่ง

	\begin{algorithm}
	\caption{Find a theta notation in terms of $n$ for the number of times the statement $x := x + 1$ is executed.}
	\begin{algorithmic}
	\State $j:=n$
	\While{$j \ge 1$}
		\State \textbf{begin}
			\For{$i:=1$ \to $j$}
				\State $x:=x+1$
            \EndFor
            \State $j:=\lfloor\frac{j}{2}\rfloor$
		\State \textbf{end}
    \EndWhile
	\end{algorithmic}
	\end{algorithm}
	

• แบบนี้ก็หา General term ($n$) ยากอะสิ → มีวิธีอยู่นะ Geometric Sum ไงงง! $$a+ar^1+ar^2+\dotso+ar^{n}$$ $$\boxed{\ce{S_n}=\frac{a_1(1-r^n)}{1-r}}$$

	\begin{algorithm}
	\caption{Find a theta notation in terms of $n$ for the number of times the statement $x := x + 1$ is executed.}
	\begin{algorithmic}
	\For{$i := 1$ \to $n$}
		\For{$j := 1$ \to $\lfloor\frac{i}{2}\rfloor$}
			\State $x := x+1$
        \EndFor
    \EndFor
	\end{algorithmic}
	\end{algorithm}
	

• $t(10) = 0+1+1+2+2+3+3+4+4+5$
• That is, $t(10) < 1+2+3+4+5+6+7+8+9+10$ (Upper bound)
• See that, $t(10) > 1+2+3+4+5$ (Lower bound)