Worst case for these types of search is O(mn), m length of needle, n length of haystack. It is not linear in n.

The absolute worst case is when both the needle and haystack are both composed of the same byte repeated (e.g. all zero).