Complexity specification

Posted Dec 5, 2025 9:01 UTC (Fri) by jeeger (subscriber, #104979)
Parent article: A "frozen" dictionary for Python

As Steve Dower noted, that optimization can be added later as long as the PEP does not specify that the operation must be O(n)

I might be misremembering from my Uni days, but all O(1) algorithms are also O(n), so the statement doesn't make sense. I'd be happy for someone to correct me though.

to post comments

Complexity specification

Posted Dec 5, 2025 9:29 UTC (Fri) by taladar (subscriber, #68407) [Link] (6 responses)

O(1) means constant time, O(n) means the time scales with the number of inputs.

Complexity specification

Posted Dec 5, 2025 9:55 UTC (Fri) by intelfx (subscriber, #130118) [Link] (5 responses)

> O(1) means constant time, O(n) means the time scales with the number of inputs.

Obviously, yes. What the GP is saying is that functions that are O(1) are also, strictly speaking, O(n), since the big-O notation only defines, informally, an "upper bound" on the algorithmic complexity.

(The answer here is that engineers tend to casually use the big-O notation where they really mean Knuth's Θ notation instead.)

Complexity specification

Posted Dec 7, 2025 12:29 UTC (Sun) by Baughn (subscriber, #124425) [Link] (4 responses)

And can you blame us? My keyboard does not have theta on it.

If he'd used uppercase-T instead, then we'd use it.

Complexity specification

Posted Dec 7, 2025 13:21 UTC (Sun) by excors (subscriber, #95769) [Link] (3 responses)

> My keyboard does not have theta on it.

As is often the case, Knuth solved that problem too, by inventing TeX half a century ago. Now we just need LWN to implement server-side KaTeX rendering.

Complexity specification

Posted Dec 7, 2025 13:57 UTC (Sun) by dskoll (subscriber, #1630) [Link] (2 responses)

I solved it in a horrible way. Look up "theta" on Wikipedia, then paste the result: Θ

Complexity specification

Posted Dec 7, 2025 15:10 UTC (Sun) by adobriyan (subscriber, #30858) [Link] (1 responses)

Install kcharselect or equivalent.

Complexity specification

Posted Dec 10, 2025 1:56 UTC (Wed) by raven667 (subscriber, #5198) [Link]

I will also add that GNOME Characters is a search provider, so you can enable it then just hit Meta and type "theta" and it'll return all the Unicode codepoints with "theta" in their names, arrow down to select and paste in. Very handy.