Given the following brute-force algorithm to find target string $b_1, b_2,...,b_m$ in a text $a_1, a_2,...,a_n$ such that $m\le n$,
Big-$O$ time complexity of the algorithm is as follows: If the entire text $a_1, a_2, ..., a_n$ does not contain $b_1$, then the outer while loop is executed $n-m+1$ times and the inner loop is never executed. The number of comparisons made for each iteration of the outer while loop is 3 ( $i< (n-m+1), location=\phi , b_1 = a_i$ ).
Worst-case scenario: if the text string $a_1,...,a_n$ is made up out of substrings $b_1,...,b_{m-1}$, then the inner while loop is executed $m-2$ times (as the first character would be compared and passed, etc. until we reach the one before the end of the target string) and the inner while loop is executed $\lfloor \log_{m-1}{n} \rfloor $ times before ending. The inner while loop made 4 comparisons and the outer while loop made 3 comparisons.
In total, the algorithm then makes $4(m-2)\times(4+3)\times \lfloor \log_{m-1}{n} \rfloor $ comparisons and thus since $m\le n$, the complexity is $O(n\log{n})$.
Questions:
- I guess in the inner while loop, $i$ should be set to $i = i + (j-1)$, so that $i$ starts at the index that mismatches the character in $b$.
- Why in the solution the inner while loop is executed $\lfloor \log_{m-1}{n} \rfloor$?
- Why we have the term $4(m-2)$? I think $(4+3)$ in $(4+3)\times \lfloor \log_{m-1}{n} \rfloor $ is back to 3 comparisons the outer loop made and 4 comparisons and inner made, but again why we have $4(m-2)$?
