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.
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
The property ____ provides a setting for the associated feature (e.g., yellow for the color property).
A. key B. value C. parameter D. element
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.
Click item A in the accompanying figure if you want to expand the files list.
Answer the following statement true (T) or false (F)