- $T_{ls,\text{worst}}(n) \in \Theta(n)$
- $T_{ls,\text{worst}}(n) \in \Omega(1)$
- $T_{bs,\text{worst}}(n) \in O(n)$
- $T_{bs,\text{worst}}(n) \in \Omega(\lg n)$
- $T_{ls,\text{best}}(n) \in \Omega(n)$
- $T_{ls,\text{best}}(n) \in \Theta(1)$
- $T_{ls,\text{best}}(n) \in O(n)$
- $T_{bs,\text{best}}(n) \in \Omega(n)$
- $T_{bs,\text{best}}(n) \in O(\lg n)$
- $T_{bs,\text{best}}(n) \in O(n)$

Input: $A$ and $B$, both sorted arrays of $n$ ints

Output: $j$, the least index such that $B[j]$ is not an element of $A$, or 'NOT FOUND' if no such element of $B$ exists

j = -1, k = 0 while k ≠ NOTFOUND and j < n-1 do j = j + 1 k = search(A,0,n-1,B[j]) ← we assume "search" is an algorithm for the search problem, with if k = NOTFOUND the tweak that search(A,left,right,x) searches A[left],...,A[right] return j i.e. we don't always start at index 0. We could equally easily use else linearSearch, binarySearch or gallopSearch. return NOTFOUNDI recommend tracing through this algorithm on sample arrays like:

A: 3 5 6 11 15 16 17 20 where n = 8 B 3 5 11 15 17 18 20 21Here's your problem: give a loop invariant for the while loop that would allow you to prove that this algorithm is correct.

Consider the problem *Unique Destination* that takes a forest on
$n$ nodes, $\{0,\ldots,n-1\}$, and
a starting node $s$ and returns TRUE if $s$ has a unique
destination, and FALSE otherwise. The forest is repesented by
an array $P$ of length $n$ where $P[i] = j$ means that node
$i$'s parent is node $j$, when $j \neq -1$, and $i$ is a root
node if $P[i] = -1$. See the image to the right to see an
example drawn out.

The following algorithm solves the *Unique
Destination*. Analyze its best and worst case running
time. Note: The outer while loop does indeed terminate, as
long as the input really is a forest (i.e. no loops). If it
were to go on too long, you would eventually hit a node you'd
already visted, which would mean there was a loop.

Algorithm:uniqueDest(P,n,s) Inputs: P an array of n integers such that P[i] = j means that the parent of node i is node j if j ≠ -1, and i has no parent otherwise s the starting node Output: TRUE/FALSE a solution to theUnique Destinationproblem next = s, count = 1 while count == 1 do curr = next count = 0, i = 0 while i < n do ← in this loop we count the number of children of curr and set next to the most recently seen child if P[i] == curr count = count + 1 next = i i = i + 1 if count == 0 return TRUE else return FALSE

while i < n and count < 2 doHow would that change the best and worst case running time functions?