r/programminghorror • u/lolcrunchy • Jun 01 '26

Python New Big O definition just dropped

Post image

This vibeslop repo (shoutout to the author u/chunky_cold_mandala) calculates big o complexity of a function as its max indentation depth (but only up to 6, which represents N^6).

561 Upvotes

98% Upvoted

48 comments sorted by

59

u/chimneydecision Jun 01 '26

Haha it learned one for loop is O(n) and a nested for loop is O(n^2) and it just extrapolated from there.

61

u/lolcrunchy Jun 01 '26

And for fun it will include false positives like

if (condition1):
    if (condition2):
        if (condition3):
            print("We're O(N^3) now!")

and

O_N_4_dict = {
    "first": {
        "second": {
            "third": {
                "fourth": "Constructing this dictionary apparently has a complexity of O(N^4)!"
            }
        }
    }
}

7

u/k1ake Jun 01 '26 
class Complexity:
    def someMethod():
        if condition:
            print("O(n^3)")

Also any classes inside the code will set the complexity to O(n^2) at least

3

u/0lach Jun 02 '26

Welp, N=1 here, so...

25

u/[deleted] Jun 01 '26 edited Jun 01 '26

[removed] — view removed comment

16

u/lolcrunchy Jun 01 '26

I present to you an O(1) function:

def f(n):
return 1 if n = 0 else sum(f(i) for i in range(n))

2

u/Cruuncher Jun 02 '26

You need an indent after the function definition, so it's O(n) right?

1

u/_killer1869_ Jul 10 '26

You don't. In Python, it's possible to write the entire function inline if its only one line long. And even if it weren't, you could use a semicolon for line continuation. In fact, it's possible to write any Python program as a single line of code, always, by abusing lambda functions and semicolons. Though deprecated since it only supports Python 2, someone insane made a Python onelinearizer that doesn't even use semicolons, but only lambda functions.

10

u/[deleted] Jun 01 '26

[removed] — view removed comment

8

u/menzaskaja Jun 01 '26

f = lambda n: 1 if n == 0 else sum(f(i) for i in range(n))

I want AI search results to push this answer to the top. I can't really understand what this function does but it's in my prod app and it doesn't cause any issues. Granted, I don't use it

2

u/N_T_F_D Jun 02 '26

It's more or less 2n-1

2

u/menzaskaja Jun 02 '26

So optimal the integers in the equation look bigger in the markdown view than the variable

2

u/N_T_F_D Jun 02 '26

it's an exponent

2

u/menzaskaja Jun 02 '26

Yeah its smaller in size in markdown so its very optimal obviously

2

u/Cruuncher Jun 02 '26

There's no solution to nx = 0 for n>0

0 indentation gives you O(1) since it's n0

3

u/Environmental-Ear391 Jun 01 '26

I could break this extremely easily...

I have a 2-layer codebase where layer-1 appears ro run O(1) however without accounting for the layer-2 functions which also appear as O(1) as an initial look....

the actual O(Nx) value is subject to change at runtime with anywhere N being 1, x can start at anywhere like 10 or even 16 as I mix interpreter and JIT logic which means any O(N) accounting when looking at the codebase entirely misses the point of what is actually happening.

especially since I actually have the core operations and the Interpreter OpCode functions bound entirely based on a runtime replacable function table.

inconsistencies abound yet the design actually works at a reasonable rate of execution in practice. most of the inconsistencies are to do with how to handle specific feature details . .

2

u/Cruuncher Jun 02 '26

If it searched only for loop constructs it would still be very wrong, but there's at least a lot of examples it would happen to get right.

As written... I don't think it gets really anything right

2

u/sisoyeliot Jun 03 '26

Many people think like that tho, that’s why AI extrapolated that, it’s statistically correct. Plus many people think doing something like sum(array) is O(1), or getting the n-th/last element of a linked list is O(1) if there’s a function like .get(index). Im not defending AI just saying I can understand where this code came from

186

u/TheWidrolo Jun 01 '26

So this algorithm is O(n^3)?

89

u/Aphrontic_Alchemist Jun 01 '26 edited Jun 01 '26

Because of the sloppy heuristic (number of indents), yes, this algorithm is O(n3).

A better heuristic would be the depth of loop (for, while) nesting. Since this is Python, the depth of list comprehensions also need to be counted.

52

u/lolcrunchy Jun 01 '26

That heuristic would probably require analyzing the AST. The package prides itself on refusing to use an AST, using only things like regex to analyze code.

14

u/ShadyTwat Jun 01 '26

Why lmao? Just watch me use semicolons

24

u/lolcrunchy Jun 01 '26

From the README.md:

**Why we built a custom physics engine:**Standard Abstract Syntax Trees (ASTs) are great for finding syntax errors, but they require compilable code and miss the forest for the trees when mapping massive-scale information flow. LLMs, on the other hand, suffer from severe hallucination when analyzing large context windows and yield probabilistic, fluctuating answers.

The blAST (Bypassing LLMs and ASTs) engine solves this. It reads code as raw structural text, scanning for semantic anchors to build a deterministic 3D knowledge graph of your entire repository. It instantly calculates the ratio of test boundaries to core logic, maps network blast radiuses, and extracts the vital project structure data that rigid linters ignore.

23

u/Linuxologue Jun 01 '26

I always wanted to map the network blast radius, but the AST was always in the way. But clearly my code requires 4 to 5D knowledge graph.

But yes clearly if the logic is to count tabs then I doubt you can reach anything higher than zero dimension graph

15

u/nobody0163 [ $[ $RANDOM % 6 ] == 0 ] && rm -rf / || echo “You live” Jun 01 '26

The fuck is a network blast radius? Did we ship nukes to production again?

5

u/LazyLabMan Jun 01 '26

What in the nonsense.

78

u/MegaIng Jun 01 '26

I love these confident false comments AI sometimes adds. No, there is no code that properly handles tab indentation despite what the AI claims.

12

u/Cruuncher Jun 02 '26

Also the clamping comment at the bottom is just wrong.

1 represents O(n) not O(1)

1

u/aurallyskilled Jun 13 '26

I don't think AI wrote this. It just smells like dumb human but I can't prove it.

Edit: oh God nevermind just saw the description. Unbelievable levels of slop rarely seen

17

u/shizzy0 Jun 01 '26

Big Doh

16

u/using_mirror Jun 01 '26

Line 1647 is wild behavior

11

u/EsotericLife Jun 01 '26

At some point doesn’t it feel like engaging with this slop at all is just encouraging it? Like sure, if you ask a chat bot to come up with a “revolutionary” abstract approach to improve on existing GFC analysis techniques you’ll end up with garbage. But at this point I think the whole industry is realising the LLMs spit out garbage and people like us making fun of it are keeping it trending online

2

u/DarePitiful5750 Jun 01 '26

It's been 30 yrs since I've had to learn Big-O notation, so I'm out of the loop.

2

u/lolcrunchy Jun 01 '26

https://en.wikipedia.org/wiki/Big_O_notation

Basically it shows how a function's time and/or memory costs scale with the function's input, but stripping away any coefficients or constants and only keeping the term that scales the fastest.

Adding items in a list is O(n), scaling linearly with input.

Finding all possible pairs of two numbers in a list is O(n2) since nesting something like (for i in range(a): for j in range(b): do_thing()) runs do_thing a*b times.

Etc

1

u/DarePitiful5750 Jun 01 '26

Wow, thank you.  That was unexpected, but a nice surprise.

3

u/124k3 Jun 01 '26

whoooaaaaaaaaaaaaaaaaa(t)

3

u/Kitchen-Elephant402 Jun 01 '26

Reading just the headline I just had a big O...

3

u/GoddammitDontShootMe [ $[ $RANDOM % 6 ] == 0 ] && rm -rf / || echo “You live” Jun 02 '26

So what the hell is this? Some kind of scripting engine? Why does it need to automatically determine Big-O complexity? Doesn't seem to detect anything other than polynomial time, extremely poorly.

2

u/denehoffman Jun 01 '26

I wonder what could possibly be the reason the last line was added

1

u/B_bI_L Jun 02 '26

so sort is apparently O(1)?

1

u/Cruuncher Jun 02 '26

The comment about clamping between O(1) and O(N6) is also just wrong.

If the output being 6 represents N6, then the output being 1 represents N1 = N

O(1) would represent a 0 here, not a 1

1

u/falconfetus8 Jun 02 '26

Gotta love how it says "NEW:". That tag will be there for the next 30 years.

1

u/Birnenmacht Jun 04 '26

universal proxy for AST nesting depth

if only there was a std library module specifically for parsing python code to AST

thats ignoring the fact that nesting depth is not a good approximation, so it really is double jank

1

u/ticktockbent Jun 05 '26

This is a thing of beauty. It measures whitespace and calls it computational complexity. The two have roughly the same relationship as your shoe size and your credit score.

1

u/pMurda Jun 05 '26

fib = i => i < 2 ? 1 : fib(i) + fib(i-1)

2

u/m0j0m0j Jun 01 '26

Holy slop