What is the best case for a pattern P and string T in string matching?

a. O(n)
b. O(log n)
c. O(m log n)
d. O(n^2)


a. O(n)
O(n) is for the string text T, and a pattern P of one character or O(m) = 1, so for O(n*m) or O(n+m) the time is O(n) or O(n+1) = O(n). Thus, for a single character pattern P on a string text T of length O(n), the best performance is O(n) or linear time.

Computer Science & Information Technology

You might also like to view...

Owners of ________ code usually place some restrictions on its use, such as acknowledging the original writers of the code or limiting it to non-commercial use

A) HTML B) PHP C) copyrighted D) open source

Computer Science & Information Technology

The property ____ provides a setting for the associated feature (e.g., yellow for the color property).

A. key B. value C. parameter D. element

Computer Science & Information Technology

The LEFT function returns the characters starting from the left side of the string up to the first space

Indicate whether the statement is true or false.

Computer Science & Information Technology

Click item A in the accompanying figure if you want to expand the files list.

Answer the following statement true (T) or false (F)

Computer Science & Information Technology