**from the presentation:**

Time complexity: O(m) operations to compute the two finger prints

finger print(P[0..m-1]) and finger print(T[0..m-1]).

O(m) operations for both, Additional n − m − 1 finger prints to

compute, each taking O(1) operations. Total cost is

O(n) + O(m)= O(n + m).

רציתי לדעת מדוע הסיבוכיות היא O(n+m ולא O(n.

השאלה שלי היא מפני שככל שגודל הקלט m (הקלט של התת מחרוזת אותה מחפשים) גדול יותר כך מס' האיטרציות בקוד קטן בהתאמה.

ניתן לראות שיש O(m)k סיבוכיות לחישוב fp של התת מחרוזת ואילו שאר הן בזמן של O(1 ולכן לא ברור לי למה

O(n+m) = O(n )+O(n-m-1