Большой O zfill в Python?

Реализация Python zfill живет здесь.

Здесь относительно очевидно, что реализация в основном состоит из распределения и memset/memcpy, а остальное — очень простое сложение/вычитание.

Большой O этих операций управляется платформой/реализацией/обстоятельствами и часто не зависит от длины строки (они могут происходить мгновенно. Они могут выделять новую страницу для кучи и запрашивать доступ к дополнительной памяти от внешних служб, занимающих несколько секунд). Но для ваших целей я бы действовал так, как будто это O(n), где n — размер результирующей строки, поскольку это, вероятно, то, что есть у memset/memcpy (как обсуждалось здесь, alloc на самом деле не измерим).

Но по правде говоря, вам, вероятно, не стоит беспокоиться об этом, поскольку вы ничего не можете сделать, чтобы изменить это. Ручная реализация, безусловно, будет медленнее.