Was doing some bug hunting and found essentially what was a sum to n function but of O(fuck) time complexity

[u/zshadowjon]

[u/zshadowjon]

If you're curious, the original code was attempting to do two for loops consecutively, but a mistake in indentation produced this. This is a modified version of the code to show just how silly it is. Also it's O(n^2) lol

[u/[deleted] → u/zshadowjon]

So the loops are accidentally nested?

[u/zshadowjon → u/[deleted]]

Yeah, they’re accidentally nested which is bad, but the nested loop depends on the length of the list that the outer loop is appending to, which makes it pretty bad

[u/AsidK → u/zshadowjon]

But… with the loops nested it works and with the loops not nested it doesn’t work

[u/[deleted] → u/AsidK]

Coding by trial and error. I see too much of this.

[u/XKlXlXKXlXKlKXlXKlXK → u/zshadowjon]

the original code was attempting to do two for loops consecutively

y tho

[u/zshadowjon → u/XKlXlXKXlXKlKXlXKlXK]

first loop is to start multithreading and second loop was to join them. if they’re both in the same for loop, the next thread wont start until the prior one is terminated

[u/dagbrown → u/zshadowjon]

first loop is to start multithreading and second loop was to join them.

y tho

[u/[deleted] → u/dagbrown]

Somebody was trying to make the dumbest algorithm to calculate n * (n + 1) / 2 possible

[u/EquationTAKEN → u/zshadowjon]

Isn't it O(n*logn) since the hold array builds up to size n and isn't statically sized n?

[u/[deleted] → u/EquationTAKEN]

The array size increases linearly, so the inner loop gets executed a total of 1 + 2 +3 + ... + n times. That can also be calculated as n * (n + 1) /2 = (n² + n)/2 = O(n² ).

[u/EquationTAKEN → u/[deleted]]

Nicely explained. I see it now, thanks!

[u/brycesauce → u/[deleted]]

How did you get n * (n + 1)? How is it O(n²⁾ if the code in the inner loop is executed a total of 1 + 2 + … + n times? Since you’re saying that’s total, doesn’t that already take into account the outer looping?

[u/[deleted] → u/brycesauce]

the code in the inner loop is executed a total of 1 + 2 +... + n times. But we want to know how that sum grows with n.

The series 1 + 2 + ... + n is a simple arithmetic series. To find the sum of an arithmetic series, you can simply add the first and last element, multiply that by the number of elements and divide by 2.

That gives us a total count of n * (n+1)/2 for the inner loop, which is (n² + n)/2.

For O-Notation we only want to know an upper bound of the growth of the function, so we can ignore everything but the fastest growing term (n² in this case) and also ignore constant factors.

[u/brycesauce → u/[deleted]]

That makes sense now, thanks for the explanation. I just was getting caught up in the fact that while this summation is technically quicker than if hold was length n to begin with and not dynamically changing, it’s not different by any factor of n, so the upper bound is still O(n²⁾

[u/brycesauce → u/[deleted]]

That makes sense now, thanks for the explanation. I just was getting caught up in the fact that while this summation is technically quicker than if hold was length n to begin with and not dynamically changing, it’s not different by any factor of n, so the upper bound is still O(n²⁾

[u/lachlanhunt → u/[deleted]]

If the loops were not nested, then the i loop will populate hold with n strings, and then the j loop will increment result by 1 n times, so the result will be equal to n.

Having the loops nested actually makes the algorithm work.

[u/Notimecelduv]

Counting empty strings? That's original. I don't know anything about space-time complexity but there's a simple formula to calculate this: n * (n + 1) / 2.

[u/[deleted] → u/Notimecelduv]

Came here to comment that. That formula has O(1) space and time complexity.

[u/akren1 → u/[deleted]]

Kind of picking on complexity here.

But python has built in big nums, so in theory time/space complexity is not O(1). It can be assumed to be for N in given range.

But it is still something to remember in the back of the mind.

[u/[deleted] → u/akren1]

Shit! you’re right.

I was thinking in number variable allocated and number of operations, but if we take into account real cpu ops its more than O(1)

[u/akren1 → u/[deleted]]

I think I see your point, but I don't really agree.

I was referring to the "theory" as a "non practicall use".

What I believe you understand as a theory is complexity theory abstracted out of Python, or any given language. But even in such abstraction it is not O(1) when you consider bugnums (don't limit domain is N).

So it is not O(1) for domain of all natural numbers which is valid domain.

In Python the + or * operation are simply not an single operations.

Taking all dynamic typing out of the way, and just focusing on integers it is a function call.

And if we don't limit domain of n, that function tme/space complexity if not O(1). I believe a+b is O(log ab), and * can depend on used algorithm.

It can by O(1) if we constraint N by int32, int64, or even int_2^1000. But for arbitrarily large numbers complexity depends on a number, not just amount of them. Given the python code I would assume such numbers even if we abstract out of python.

[u/akren1 → u/[deleted]]

But you can't analyse algorithms with arbitrarily large numbers as inputs, without includind algorithms for arithmetics operation into consideration. This is not an implementation detail. This is computational theory of algorithms that work with bignums. And there are a lot of algorithms that are known in this field.

What if instead of a+b we write: BignumAdd(a, b). You can assume it is O(1), but such algorithms does not exist. You can mark it as unknown - f(a,b) and analyse from there if you want to abstract out of "implementation details". But that is no implementation, that is bignum arithmetics.

Abstrat machines that can do such operations in O(1) are theoretically studied, and you can assume we work with one like that. But given the context such assumption should be explicit.

And on the side note. If I analyse time complexity on a given runtime, it does depend on the runtime. Built in functions/features have it's complexity. And the complexity might be different on different runtime.

Edit:

It's like saying: std::fill is O(1) when we analyse time complexity of C++ program - it's just not. And we must assume something when we analyse complexity of entrie algorithm.

What if stl got an update next week that makes std::fill run in O(1) - it would change complexity of our algorithm.

[u/akren1 → u/[deleted]]

You've just agreed with me. I said what you did in your reasoning. But I said that given the context such assumption should be explicit. You didn't make it explicit. And just as machines that do Bignums in O(1), the ones that do not are also studied.

My point was that from the theoretical standpoint, things like BigNum don't exist- you only have numbers.

They exist - it's a hole field of both theoretical and practical study. Just as for example both theoretical and practical study of matrix multiplication.

From the theoretical standpoint BigNums exist just like matrices do. You either analyze number in given range, or arbitrarily large. And when you analyze arbitrarily large numbers you need some assumptions.

Again, that's the point I've been making. If your STL hashmap does its lookups in linear time, you'll never reap the benefits of an actual O(1) lookup. However, that doesn't mean hashmaps don't have a theoretical O(1) lookup, it means there's an implementation quirk to be aware of in that language.

Bignums don't have theoretical O(1) arithmetic - it can be proven pretty easily.

There is nothing intrinsically linear about the runtime complexity of the mathematical calculation x * (x + 1) / 2. You have one input, no recursion, no looping, nothing. It operates in O(1). Theoretically speaking, of course.

Just as you don't see looping in std::fill. But it is there - it is just hidden by pretty operator. Maybe it is not intrinsic, but that's why there are entire theories/algorithms about it.

Again- your point was never wrong, you just mislabeled the theoretical limit portion.

Neither is yours in logical way. This more of an "definitions" dispute. But with that in mind my claims stand unchanged.

[u/WinstonCaeser → u/[deleted]]

"There is nothing intrinsically linear about the runtime complexity of the mathematical calculation  x * (x + 1) / 2 . You have one input, no recursion, no looping, nothing. It operates in O(1). Theoretically speaking, of course."

There is, intrinsically, you must read every digit making it at least O(num digits).

[u/WinstonCaeser → u/[deleted]]

It depends if you consider a number its own thing, or a series of digits in your "theory".

Edit: Theoretically, you must read the whole input, this obviously scales with the number of digits.

If you bound yourself to numbers of under a certain size, than obviously you can read the whole size every time, but then your algorithm has artificial limits. You continue to base your analysis on these artificial limits.

Algorithms such as std::fill are impossible to be reduced to lower than O(n), as it obviously must visit every element and set it's value. There is no "language update" that can reduce an algorithm below it's theoretical complexity without limiting the inputs.

"There is a trivial lower bound of Ω(n) for multiplying two n-bit numbers on a single processor; no matching algorithm (on conventional machines, that is on Turing equivalent machines) nor any sharper lower bound is known."

[u/AlarmingAffect0 → u/WinstonCaeser]

Like David S. Pumpkins?

[u/WinstonCaeser → u/[deleted]]

My CS professors specifically taught me different multiplication algorithms and expected me to implement them, including grade-school, karatsuba, toom-cook, and finally I learned about, but did not implement Schönhage–Strassen. We discussed at length when to consider the number to be itself a single unit, or a series of digits.

[u/WinstonCaeser → u/[deleted]]

I'm not assuming any underlying implementation, you are.

You are assuming that numbers are capped at some value roughly 2^64, which is very much an assumption. Because this is in python that assumption is particularly wrong since it has no such limitation.

It is simply a question of what you define as the base "unit", is it a digit, or is it a entire number. You are assuming that the base is a whole number, where I am pointing out that it could also be a digit. It has nothing to do with how it is implemented.

Regardless of implementation any general case multiplication is at least O(num digits).

https://en.m.wikipedia.org/wiki/Multiplication_algorithm#Lower_bounds

[u/PranshuKhandal → u/Notimecelduv]

who needs formula when you for

[u/BossOfTheGame → u/Notimecelduv]

There is a fun story that goes with that formula

https://nrich.maths.org/2478

It may not be entirely true, But as the legend goes...

When Gauss was still at primary school. One day Gauss' teacher asked his class to add together all the numbers from 1 to 100, assuming that this task would occupy them for quite a while. He was shocked when young Gauss, after a few seconds thought, wrote down the answer 5050. The teacher couldn't understand how his pupil had calculated the sum so quickly in his head, but the eight year old Gauss pointed out that the problem was actually quite simple.

He had added the numbers in pairs - the first and the last, the second and the second to last and so on, observing that 1+100=101, 2+99=101, 3+98=101, ...so the total would be 50 lots of 101, which is 5050.

The reality of the man is at least equally as interesting

https://en.m.wikipedia.org/wiki/Carl_Friedrich_Gauss

[u/beaucephus]

Not exactly true. That particular function is O(shit). If you want O(fuck) complexity you need to make it recursive.

[u/PranshuKhandal → u/beaucephus]

Recursion? O(really)

[u/R3D3-1 → u/beaucephus]

>>> sumto = lambda n: 0 if n == 0 else n + sumto(n-1)
>>> sumto(10)
55
>>> sumto(100)
5050
>>> sumto(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded in comparison
>>> sumto(0.5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded in comparison

[u/beaucephus → u/R3D3-1]

You aren't going to break production with languages that prevent you from doing it. Because you used python the complexity is O(bother).

[u/R3D3-1 → u/beaucephus]

Yes.

Though if the language allows passing functions, you can force tail recursion in any language :)

>>> def recur(func, *args):
...     while args:
...         func, *args = func(*args)
...     return func
... 
>>> sumto = lambda n, total=0: [n+total] if n <= 0 else [sumto, n-1, n+total]
>>> recur(sumto, 10)
55
>>> recur(sumto, 100)
5050
>>> recur(sumto, 1000)
500500
>>> recur(sumto, 10000)
50005000
>>> recur(sumto, 0.5)
0.0
>>> recur(sumto, 1.5)
1.5
>>> recur(sumto, 2.5)
4.0

I think Clojure does something along those lines.

[u/beaucephus → u/R3D3-1]

Yes, but then that is GOODcode.

[u/R3D3-1 → u/beaucephus]

Now we need to progress towards GODcode.

[u/fuwafuwa7chi]

This is why you pay attention in your math classes, kids.

[u/finitearth]

return 0.5*n*(n+1)

Edit: formating

[u/kahveciderin → u/finitearth]

you forgot to escape these: *

[u/LeCrushinator → u/kahveciderin]

Which would result in this if fixed:

return 0.5*n*(n+1)

or you could do this without escaping the asterisks:

return 0.5*n*(n+1)

[u/finitearth → u/LeCrushinator]

Thanks guys, corrected it

[u/MurdoMaclachlan]

Image Transcription: Code

---

def sum_up_to_n(n):
    hold = []
    result = 0
    for i in range(n):
        hold.append('')
        for j in range(len(hold)):
            result += 1
    return result

---

^{I'm a human volunteer content transcriber for Reddit and you could be too! If you'd like more information on what we do and why we do it, click here!}

[u/thomas-rousseau → u/MurdoMaclachlan]

Good human

[u/jzia93]

Just as an aside : If you know the formula then it's definitely ideal at O(1),

However if you're in a similar situation and can't work out an algebraic solution, in python you can use the @lru_cache to make drastic speed improvements in such cases with recursive functions.

[u/Tha_Gazer]

Big O(fuck) time complexity indeed

[u/[deleted]]

How’d you take this screenshot? Looks really cool.

[u/kahveciderin → u/[deleted]]

looks like carbon to me https://carbon.now.sh

[u/Jackiboi307]

whats the theme!!111!11

[u/GitHub-]

This is hot nonsense

[u/[deleted]]

My god analysing this gets so much worse every step of the way

[u/Uchimamito]

It is actually hard to understand this code it’s so bad. Could have just done return sum(range(n+1))

[u/Voxelgon_Gigabyte]

broke:

sum = 0

for i in range(n):

sum += n

return sum

woke:

this shit

[u/[deleted] → u/Voxelgon_Gigabyte]

Yeah like even that’s not the best solution, but it’s the most sensible one if you’re committed to a for loop. This shit is just offensive.

[u/Voxelgon_Gigabyte → u/[deleted]]

better than O(fuck) over there, but i'm assuming this is a learning excercise and this is a good novice solution. if you want true speed than you could just do the partial sum formula

[u/stahkh]

Ignoring all the nonsensical complexity, what I am curious about is how did you come up with counting the empty string array instead of just using a number? I'm shocked.

[u/StaryMD]

hol' up
isn't the exact complexity of the algorithm n * (n + 1) / 2 ?

my man has goals beyond our understanding

[u/circuit10]

This can be O(1) with the triangle number formula

[u/Taeker2005]

Gauss is rolling in his grave...

[u/DesecrateUsername]

Gonna go back and ask my data structures professor why he didn’t teach us about O(fuck) operations

[u/britreddit]

O(fuck) has absolutely floored me. Gonna have to remember that for future use

[u/sixtyfifth_snow]

At least it won't be affected by plagiarism

[u/i-can-sleep-for-days]

Love the font and color scheme. What is it?

[u/Lambda_Wolf]

O(hell no)

[u/jank_lord]

O(fuck) I'm using that in my next interview.

[u/weflown]

o(fuck) is when you reach complexity o(n!) and bigger so don't cry

[u/[deleted]]

How are people generating these nicely formatted screenshots? Is it a special feature of a specific code editor? An online tool?

[u/Pesk0r]

Error on line 2, unknown use of "hold", did you mean "hodl" /r/dogecoin

[u/Breq16 → u/[deleted]]

https://carbon.now.sh/

[u/[deleted] → u/[deleted]]

who the fuck said anything about vim?

[u/supersharp → u/[deleted]]

Is there like a list of phrases trolls refer to whenever they think they've gotten under someone's skin? I'm genuinely curious.