Assignment: Asymptotic Notation & Searching / String-Matching Algorithms (With

Simulation)

1) Asymptotic Notation

Objective

To express algorithm growth rates as input size n increases.

Key Notations

• Big-O (O): upper bound (worst-case growth)

• Big-Ω (Ω): lower bound (best-case growth)

• Big-Θ (Θ): tight bound (exact growth class)

Definition (Concept Form)

Big-O: f(n) ≤ c·g(n) for n ≥ n0

Omega: f(n) ≥ c·g(n) for n ≥ n0

Theta: c1·g(n) ≤ f(n) ≤ c2·g(n) for n ≥ n0

Simulation Example (Growth Comparison)

Let:

• f(n) = 3n² + 10n + 5

• g(n) = n²

For large n (e.g., n=10,100):

• f(10)=3(100)+100+5=405, g(10)=100

• f(100)=3(10000)+1000+5=31005, g(100)=10000

So f(n) grows like n² ⇒ f(n) = Θ(n²).

Part A: Searching Algorithms

2) Linear Search

Pseudocode

LINEAR_SEARCH(A, n, key)
 FOR i ← 0 TO n-1

IF A[i] = key

RETURN i

RETURN -1

Simulation (Dry Run)

Let A = [12, 7, 19, 3, 25], key = 3

Step i A[i] Compare A[i]==3 Result

1 0 12 No continue

2 1 7 No continue

3 2 19 No continue

4 3 3 Yes Return 3

Time Complexity: O(n)

3) Binary Search (Sorted Array Required)

Pseudocode

BINARY_SEARCH(A, n, key)

low ← 0

high ← n-1

WHILE low ≤ high

mid ← (low + high) / 2

IF A[mid] = key

RETURN mid

ELSE IF A[mid] < key

low ← mid + 1
 ELSE

high ← mid - 1

RETURN -1

Simulation

Let A = [3, 7, 12, 19, 25], key = 19

Step low high mid A[mid] Action

1 0 4 2 12 12 < 19 ⇒ low=3

2 3 4 3 19 Found ⇒ Return 3

Time Complexity: O(log n)

Part B: String Matching Algorithms

We will use the same test case for all string algorithms:

• Text (T) = "ABABDABACDABABCABAB"

• Pattern (P) = "ABABCABAB"

Pattern length m = 9

4) Brute Force String Matching

Pseudocode

BRUTE_FORCE_MATCH(T, P)

n ← length(T)

m ← length(P)

FOR i ← 0 TO n-m

j←0
 WHILE j < m AND T[i+j] = P[j]

j←j+1

IF j = m

RETURN i

RETURN -1

Simulation (Key Steps)

Try matching P starting from T index i:

• i=0: compare T[0..] with P:

o ABAB matches first 4 chars, then mismatch occurs ⇒ shift

• i=1,2,... keep shifting

• When i=10:

o T[10..18] = ABABCABAB

o P = ABABCABAB

o Full match ⇒ Return 10

Output: Match found at index 10

5) Rabin–Karp (Rolling Hash)

Idea

Compare hash(P) with hash(window of T). If hashes match, verify actual characters.

Pseudocode

RABIN_KARP(T, P, d, q)

n ← length(T), m ← length(P)

h ← d^(m−1) mod q

pHash ← 0, tHash ← 0
 FOR i ← 0 TO m−1

pHash ← (d*pHash + P[i]) mod q

tHash ← (d*tHash + T[i]) mod q

FOR i ← 0 TO n−m

IF pHash = tHash

IF T[i..i+m−1] = P

RETURN i

IF i < n−m

tHash ← (d*(tHash − T[i]*h) + T[i+m]) mod q

IF tHash < 0: tHash ← tHash + q

RETURN -1

Simulation (Small Demonstration with Numbers)

To “simulate” easily, we choose:

• d = 10, q = 101

• map letters: A=1, B=2, C=3, D=4 (demo mapping)

Compute hash of pattern and rolling windows (concept):

1. Compute pHash

2. Compute tHash for first window

3. Slide window by 1:

o Remove left char effect

o Add next char effect

4. When tHash == pHash, do character check.

At i=10, window equals pattern ⇒ hash match ⇒ verification passes ⇒ Return 10

6) KMP Algorithm

Idea

Avoid re-checking matched characters using LPS array (Longest Prefix which is also Suffix).

(a) LPS Computation Pseudocode

COMPUTE_LPS(P)

m ← length(P)

LPS[0] ← 0

len ← 0

i←1

WHILE i < m

IF P[i] = P[len]

len ← len + 1

LPS[i] ← len

i←i+1

ELSE

IF len ≠ 0

len ← LPS[len−1]

ELSE

LPS[i] ← 0

i←i+1

RETURN LPS
LPS Simulation for P = "ABABCABAB"

Index: 0 1 2 3 4 5 6 7 8
Char : A B A B C A B A B
LPS : 0 0 1 2 0 1 2 3 4

(You can show short reasoning: when mismatch happens, KMP jumps using LPS.)

(b) KMP Matching Pseudocode

KMP_MATCH(T, P)

n ← length(T), m ← length(P)

LPS ← COMPUTE_LPS(P)

i ← 0, j ← 0

WHILE i < n

IF T[i] = P[j]

i←i+1

j←j+1

IF j = m

RETURN i − j

ELSE IF i < n AND T[i] ≠ P[j]

IF j ≠ 0

j ← LPS[j−1]

ELSE

i←i+1

RETURN -1
Simulation (Key Jump)

• KMP matches several characters

• When mismatch occurs, it does j = LPS[j−1] instead of shifting i back

• Eventually finds full match starting at i=10 ⇒ Return 10

Time Complexity: O(n+m)

7) Z Algorithm

Idea

Build Z array where Z[i] = length of longest substring starting at i which matches prefix of S.

For pattern matching, build:

• S = P + "$" + T

Z Pseudocode

Z_ALGORITHM(S)

n ← length(S)

Z[0] ← 0

L ← 0, R ← 0

FOR i ← 1 TO n−1

IF i > R

L←R←i

WHILE R < n AND S[R-L] = S[R]

R←R+1

Z[i] ← R − L

R←R−1

ELSE

k←i−L
 IF Z[k] < R − i + 1

Z[i] ← Z[k]

ELSE

L←i

WHILE R < n AND S[R-L] = S[R]

R←R+1

Z[i] ← R − L

R←R−1

RETURN Z

Simulation (Matching)

Create:

• S = "ABABCABAB$ABABDABACDABABCABAB"

Compute Z array.
Whenever Z[i] = |P| (=9) at some i, a match occurs in T.

Here, Z becomes 9 at the position corresponding to T index 10 ⇒ Match at 10.

Time Complexity: O(n)

Complexity Summary Table

Algorithm Best Average Worst

Linear Search O(1) O(n) O(n)

Binary Search O(1) O(log n) O(log n)

Brute Force (String) — — O(nm)

Rabin–Karp — O(n+m) O(nm)

KMP — O(n+m) O(n+m)

Z Algorithm — O(n) O(n)