Given a string of $n$ characters called the text and a string of $k$ characters called the

pattern $($where $kn).$ The following Brute Force algorithm returns the index of the

first character in the text that starts a matching substring or $-1$ if the search is

unsuccessful $($assuming the start index is $1)$

ALGORITHM BF$-$SM $(T[1$dotsn$],P[1$dotsk$])$

$//$ Input: An array $T[1$dots...$n]$ of $n$ characters representing a text

An array $P[1$dotsk$]$ of $k$ characters representing a pattern

$//$ Output: The index of the first character in the text that starts a matching substring or $-1$ if the search is unsuccessful

for $i=1ton-k+1do$

$j=1$

while $jk$ and $P[j]=T[i+j-1]$

a$)(3$ marks$)$ What is the best$-$case scenario for the given BF$-$SM algorithm when searching for a

pattern within a text? provide an example to illustrate this?

b$)(2$ marks$)$ What is the time complexity of the algorithm in its best$-$case scenario? $($explain

and use Big$-0$ notation$)$

c$)(3$ marks$)$ What is the time complexity of the algorithm when the length of the pattern $($k$)$ equals

the length of the text $($n$)$ in the best$-$case scenario? $($Explain why$)$