Код CPython для str.count находится в PyUnicode_Count. В современных версиях Python это отправляется на один из asciilib_count, ucs1lib_count, ucs2lib_count или ucs4lib_count в зависимости от того, как хранится строка haystrack, но в конечном итоге все они сводятся к универсальному STRINGLIB(count) код, который просто вызывает FASTSEARCH.
Если вы посмотрите на верхнюю часть этого последнего исходного файла:
/* fast search/count implementation, based on a mix between boyer-
moore and horspool, with a few more bells and whistles on the top.
for some more background, see: http://effbot.org/zone/stringlib.htm */
Для односимвольных игл это просто strchr. Для не крошечных игл, как предполагается, создается дельта-таблица Бойера-Мура, которая включает в себя фильтр Блума и некоторые другие вещи, которые линейно пропорциональны размеру иглы, плюс некоторые другие вещи, которые являются постоянными. Но нет ничего пропорционального размеру стога сена.
Итак, то, называете ли вы эту константу или линейную, зависит от того, считаете ли вы размер иглы входным или постоянным.