Complexity specification

Posted Dec 5, 2025 9:29 UTC (Fri) by taladar (subscriber, #68407)
In reply to: Complexity specification by jeeger
Parent article: A "frozen" dictionary for Python

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

to post comments

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.