If k = n - constant it comes out to O(1).
Every O(n) is O(1) if n = 1. Complexity measures worst-case by-definition, not all cases.
alt Hacker News
Every O(n) is O(1) if n = 1. Complexity measures worst-case by-definition, not all cases.