autumn geode
I am trying to determine the compelxity of this code. Since these are consecutive blocks of code would I just take the dominant term? I see that in the first block of code it is O(n^3) and then the second block of code with the if statement is O(1) I think? then taking the max of the two that would be O(n^3)?
jovial mothBOT
I am trying to determine the compelxity of this code. Since these are consecutiv...
@autumn geode
Python help channel opened
tired crown
i'm not sure. there are a few errors in the code.
tired crown
for example, line 6 is indented more than line 7
mylist[j] += 3
for k in range(n/3):```that makes it difficult to say what the program is supposed to to.
autumn geode
oh yeah I see what you are saying
I think it is best to just assume the spacing is correct in this case
because my prof's tend to make errors a lot
they're careless
unfortunately
tired crown
yes, but the question is, what is the correct spacing?
maybe like this.
for i in range(n/2):
for j in range(n):
mylist[j] += 3
for k in range(n/3):
cost = cost + mylist[k]```No i think it is supposed to be like this
for i in range(n/2):
for j in range(n):
mylist[j] += 3
for k in range(n/3):
cost = cost + mylist[k]
sorry my spacing may be off
tired crown
okay, that makes sense too.
tired crown
the other problem is the arguments for range. n/2 and n/3 are floats but range only works with ints.
autumn geode
so guess we just assume they should be floored?
They gave the answer as O(n^3) I am just trying to understand why that is because idk if I have deciphered the if block correctly and came to the conclusion correctly
tired crown
okay. that could be done with // in python3. i think python2 actually used / for that.
tired crown
They gave the answer as O(n^3) I am just trying to understand why that is becaus...
yes, i think you're right.
the if only does 50 prints max. i have no idea what the complexity of a print is, but it can't be that bad.
autumn geode
Think it would depend if how long it takes to print is dependent on the size of the list
In this case it always prints the same thing. p * p, then one value from list
So pretty sure that if block is just O(1)
That's what I want to know for certainty though
tired crown
hm. yes, it depends on the first 50 values of the list. and you modify the values with the nested loops.
autumn geode
yeah
tired crown
i suppose printing an integer is about O(log n) where n is the value of the int.
but i think you should think of it as O(1)
autumn geode
we were taught that log(n) is only when number of times loop is runned is affected by a constant multiplier or divisor at each iteration
yeah same here
tired crown
yes, i think in theory, printing an integer is affected by divisor 10 in each iteration while printing the digits.
autumn geode
ohh okay
tired crown
so actually, since you increased all values by 3*n/2 during the for-j loop, maybe it changed the complexity to something bigger than O(1). probably O(log n). but i suppose it's still less than the O(n^3) of the nested loop.
autumn geode
yeah
tired crown
if n > 50:
for p in range(50):
print(p * p + mylist[p])```has the same complexity as
```py
print(n)```due to the nested loop
teal mica
for this sort of question, we generally assume we're operating on an abstract machine where operations like print are O(1), no?
tired crown
yes, i think you're right.
teal mica
by this reasoning the p*p would be n^2
tired crown
no, p is just the numbers from 0 to 49. so they don't matter.
teal mica
my point being that multiplication is O(1) in this context, not O(n^2) or O(nlogn)
i suppose if you want a different example, cost + mylist[k] would be linear or logartihmic by the above logic
oh i suppose i misread some of your messages
apologies
tired crown
hm.. i didn't think about the cost of arithmetic yet.
tired crown
i was just confused about the use of print here and saying, that it would print log n characters, so it might matter depending of the prof.
teal mica
the answer is O(n^3) because you have 3 nested loops
the print isn't in the nested loop regardless, no?
in fact the entire if statement isn't correlated to the input size at all
tired crown
it's not in the nested loop, but the values it prints are calculated by the nested loop.
tired crown
if n > 50:
for p in range(50):
print(p * p + mylist[p])```is about equivalent to ```py
if n > 50:
for p in range(50):
print(p * p + initial_values[p] + 3 * n/2)``` or ```py
print(3 * n/2)```as n approaches infinity, the 50 become infinitesimally small and not relevant to the big O
yes, in big O all 3 of those examples would be O(1)
rancid trail
i was just confused about the use of `print` here and saying, that it would prin...
that's true, but it doesn't affect the overall complexity here since mylist[p] is certainly not on the scale of exp(n^3) (which is what it would take for print(... + mylist[p]) to be comparable to O(n^3))
tired crown
correct. i think print(n) is either O(1) or O(log n), which is both less than O(n^3).
teal mica
it might be helpful to think about what n is here
not in the function, but in the time complexity
n is the number of elements in mylist
print(X) is O(log(num_of_digits_of_X))
so you want to find the time complexity relative to the number of elements in mylist, not relative to the number of bits in len(mylist)
in that sense, print(X) may be logarithmic, but it doesn't really matter when compared to how fast the for loop grows
rancid trail
print(X) is O(log(num_of_digits_of_X))
justO(log(X))(which isO(num_of_digits_of_X))
tired crown
i'm pretty confused now where that X comes from. X=n here, right? the number of elements in the list.
teal mica
yeah i'm trying to separate out n which represents the number of elements in the list, and X which represents the integer that is the number of elements in the list..
technically, yes, X=n
rancid trail
in the sentence "print(X) is O(log(X))", X is just any number. In the example the thing being printed is p*p+mylist[p], which is, uhh.. p*p is O(1) since p is at most 50, but mylist[p] is something like O(n^2) here. So the print takes time O(log n).
teal mica
oh that's a good thought. if we use a different problem, ```py
a = [1, 2, 3]
b = a[0] * a[0]
what's the big O of this problem?
rancid trail
O(1) because there's no parameters? ;p
teal mica
it's O(1) where n is the length of a, but it's O(n^2) where n is the size of a[0]
teal mica
O(1) because there's no parameters? ;p
🍅
i edited the code to remove the print so we only talk about the multiplication
rancid trail
it's `O(1)` where `n` is the length of `a`, but it's `O(n^2)` where n is the siz...
that roughly tracks, yeah. If I'm being pedantic, I think python's int implementation has a slightly better complexity than O(log(a)*log(b)) to do a*b (Karatsuba multiplication and all that)
teal mica
i was typing something pedantic about multiplication haha but deleted it to not be confusing
technically for small integers to my knowledge a lot of the time we use the n^2 algorithm, but as we increase in integer size we heuristically use karatsuba and tom-cook and some implementations even schonhage-strassen
e.g. here's rust's bigint multiply implementation https://github.com/rust-num/num-bigint/blob/f09eee83f174619ac9c2489e3feec62544984bc5/src/biguint/multiplication.rs#L91
rancid trail
technically for small integers to my knowledge a lot of the time we use the n^2 ...
in python it's actually just karatsuba all the way up I believe: https://github.com/python/cpython/blob/main/Objects/longobject.c#L4196
jovial mothBOT
Objects/longobject.c line 4196
_PyLong_Multiply(PyLongObject *a, PyLongObject *b)```wow!
apparently it does. that's really interesting
from reading some issues on github it sounds like it's just that no one has bothered to implement more optimal algorithms, especially since there are existing alternatives that are much faster for bigints
jovial mothBOT
Python help channel closed