---
# System prepended metadata

title: Homework 1-5
tags: [Course - Algorithmics]

---

Homework 1-5
=
###### tags: `Course - Algorithmics`
## Design
* Induction on $n$, where $n = high - low + 1$ is size of array section.
* Base case, $n = 0$
	* High must be less than low (line 4), thus the algorithm returns <font color=#0000FF>**Not found**</font>.
	* Which is correct because $i$ can't be in an empty section.
* Induction hypothesis
	* Assume that for $1 ≤ SectionSize < k$, the algorithm returns <font color=#0000FF>**i**</font> (which means $i$ is in the section), otherwise it returns <font color=#0000FF>**Not found**</font>.
* Show the algorithm in a section of $k$ elements returns <font color=#0000FF>**i**</font> if it's in the section, otherwise it returns <font color=#0000FF>**Not found**</font>.
	* In this section of $k$ elements, the Algorithm executes recursive case
	* Compares `A[mid]` to `mid`.
	1. *Case 1* `A[mid] < mid`
		* Since A is sorted, $i$ must in the section ``[mid+1, high]``.
		* Which is searched recursively.
		* Thus returns result correctly by induction hypothesis, since $1 ≤ k/2 ≤ k$, and of cause for $k/4, k/8,...$
	2. *Case 2* `A[mid] > mid`
		Since `A` is sorted, $i$ must in the section ``[low, mid-1]``.
		Which are correctly searched recursively
	3. *Case 3* `A[mid] == mid`
		Algorithm returns <font color=#0000FF>**mid**</font>, which is correct because $i = mid$ and it's in the array section.
## Pseudo Code
```cpp=
procedure find_fixed_point(A : array) do
	set low = 1     // low is left endpoint of search interval
	set high = n    // high is right endpoint of search interval
	while low ≤ high do    // binary search
		set mid = ⌊(high + low) / 2⌋
		if A[mid] > mid do
			set high = mid - 1
		end
		if A[mid] < mid do
			set low = mid + 1
		end
		if A[mid] == mid do
			return mid
			break
		end
	end

	if low > high do
		return "Not found."
	end
end
```
## Analysis
### Time complexity
* Worst case (not found)
    * $\Theta(log_{2}{(n)})$
* Average case
    * We need to caculate expectation value.
        * $E[n] = \sum_{k=1}^{log_{2}{n}} k\times \frac{2^{k-1}}{n}$
        * Note that $k\times 2^{k-1} < log{_2}{n}\times 2^{k-1}$
        * Then the formula above is bounded by $\sum_{k=1}^{log_{2}{n}} log_{2}{n}\times \frac{2^{k-1}}{n} = \frac{log_{2}{n}}{n}\sum_{k=1}^{log_{2}{n}}2^{k-1}$
        * And $\sum_{k=1}^{log_{2}{n}}2^{k-1} = \frac{1-2^{log_{2}{n}}}{1-2} = 2^{log_{2}{n}}-1 = n-1$
        * Multiplying it with $\frac{log_{2}{n}}{n}$ and we can get $log_{2}{(n)}$
    * Therefore, it's also $\Theta(log_{2}{(n)})$
### Space complexity
* Any case
    * $\Theta(1)$