Data-structures 1

Complexity

Algorithm runtime #definition

\begin{matrix} Number of operations depending on the size of input is called the algorithm runtime \end{matrix}

Worst and best cases #definition

\begin{matrix} 1. & Worst case is the most number of operations algorithm can execute \\ over all inputs \\ 2. & Best case is the least number of operations algorithm can execute \\ over all inputs \end{matrix}

Average case #definition

\begin{matrix} Average case is the number of operations algorithm will execute, \\ averaged over all possible inputs \\ It is important to devise the probability distribution over inputs, \\ as the average is not just mathematical avg, it is a weighted average \end{matrix}

Example

\begin{matrix} Let us examine code of a linear search for an element k in array a r r \end{matrix}

i = 1                            # 1 time
while i <= n:                    # n+1 times
	if arr[i] == k: return True  # n times
	i += 1                       # n times
return False                     # 1 time
								 # _________
                                 # 3n + 3 in total

\begin{matrix} Worst case is 3 n + 3, when there is no element k in a r r \\ Best case is 3, when element k is first in a r r \\ Let f_{i} (n) represent runtime when k is on i -th place in a r r \\ \begin{matrix} \begin{matrix} f_{1} (n) = 3 \\ f_{2} (n) = 6 \\ ⋮ \\ f_{n} (n) = 3 n \end{matrix}} & \sum_{i = 1}^{n + 1} f_{i} (n) = 3 + 6 + \dots + 3 n = \frac{3 n (n + 1)}{2} \\ f_{n + 1} (n) = 3 n + 3 \end{matrix} \\ ⟹ Average case is \frac{3 n (n + 1)}{2 n} = \frac{3 (n + 1)}{2} \end{matrix}

Big-O, Omega, "order" of functions #definition

\begin{matrix} f (n) = O (g (n)) ⟺ & \exists α > 0 \in R, N \in N_{0} : \forall n \geq N : f (n) \leq α g (n) \\ f (n) = o (g (n)) ⟺ & \forall α > 0 \in R : \exists N \in N_{0} : \forall n \geq N : f (n) \leq α g (n) \\ f (n) = Ω (g (n)) ⟺ & \exists α > 0 \in R, N \in N_{0} : \forall n \geq N : f (n) \geq α g (n) \\ f (n) = ω (g (n)) ⟺ & \forall α > 0 \in R : \exists N \in N_{0} : \forall n \geq N : f (n) \geq α g (n) \\ f (n) = Θ (g (n)) ⟺ & f (g (n)) = O (g (n)) and f (g (n)) = Ω (g (n)) \end{matrix}

\begin{matrix} 3 n^{2} + 5 = O (n^{2}) ? \\ f (n) = 3 n^{2} + 5, g (n) = n^{2} \\ 3 n^{2} + 5 \leq 3 n^{2} + 5 n^{2} = 8 n^{2} ⟹ f (n) \leq 8 g (n) ⟹ f (n) = O (g (n)) \end{matrix}

Data structures

Array #definition

\begin{matrix} "Linear" ordered data collection with randow access by index \\ | \begin{array}{cc} 1 & 2 & 3 & \dots & n \end{array} | \end{matrix}

Stack #definition

\begin{matrix} "Linear" ordered data collection with restricted access - LIFO (Last In - First Out) \\ Stack is usually implemented as array with a counter, pointing to the "top" \end{matrix}

Parenthesis validation

\begin{matrix} e.g. "[](){}[(((<>)))]" \\ 0. Read one parenthesis \\ 1. Opening parenthesis? Push to stack \\ 2. Closing parenthesis? Pop last parenthesis on stack, check if paired \\ 2.1 If not paired (or stack is empty), abort, invalid \\ 2.2 If paired, continue to 0 \\ 3. Input is over? Check if stack is empty \\ 3.1 If empty, valid \\ 3.2 If not empty, invalid \end{matrix}

Postfix Polish notation

\begin{matrix} operand1 operand2 operation operand3 operation ... \\ e.g. 2 3 + 8 * \\ 0. Read one element \\ 1. Operand? Push to stack \\ 2. Operation? Pop n operands from stack, perform operation, push result to stack \\ continue to 0 \\ 3. Input is over? \\ 3.1 If stack has more than one element, invalid \\ 3.2 If stack has one element, it is the result \end{matrix}

Queue #definition

\begin{matrix} "Linear" ordered data collection with restricted access - FIFO (First In - First Out) \end{matrix}