it makes the object available for gc, right?
#algos-and-data-structs
austere sparrow
yes
It's an implementation detail of CPython that it will be collected right away if there are no references to it
In implementations without refcounting, it's entirely possible that it will still be collected some time after ins enclosing function ends, just like if you didn't use del
Also, foo = None does the same in regards to GC
lean walrus
del foo[1:6]
hushed river
What are some resources to learn DSA??
austere sparrow
`del foo[1:6]`
My original point was that the del keyword is largely useless
So yes, you can do del foo[1:6], but this can already be accomplished with foo[1:6] = ()
lean walrus
yes, i agree
i never used del keyword
for lists and bytearrays i can use foo[1:6] = () or foo.pop()
set's have foo.remove(item)
dict's have foo.pop(key)
i have never had to remove attributes from instances, so i never used del foo.bar. If i have to do this i will do foo.__class__.bar.__delete__(foo)
del foo is almost equal to foo = ... or foo = None
item are almost always added to collections
if you need to delete an item, it's easier and more pythonic to create a new collection without some items
fiery cosmos
hi all, trying to understand a specific step in a document from my uni. i don't know if i can redistribute or not so can someone help me and i just share my screen?
its not homework its just a help doc on how to solve a recurrence using the master theorum
im just getting lost in the math
austere sparrow
item are almost always added to collections
if you need to delete an item, it's ...
yep, I don't really see the case for __delattr__
austere sparrow
hi all, trying to understand a specific step in a document from my uni. i don't ...
nobody's going to go after you for sharing a problem from your teaching materials
that's absolutely fine
fiery cosmos
well it's online school and they're very weird about reproducing or disseminating materials.. anyhow i got someone to help me for the time being
lean walrus
what should i return in __eq__ if i dont know how to compare?
False or NotImplemented?
class X:
x: int
def __eq__(self, obj: object) -> bool:
if isinstance(obj, X):
return self.x == obj.x # implementation
return NotImplemented # this?
return False # or this?
agile sundial
NotImplemented is right
lean walrus
ok, i understand
>>> class X:
... def __eq__(self, obj: object) -> bool:
... return NotImplemented
...
>>> X() == ...
False
>>>
>>> class X:
... def __eq__(self, obj: object) -> bool:
... return 123
...
>>> X() == ...
123
>>>
>>> class X:
... def __eq__(self, obj: object) -> bool:
... return 'hello'
...
>>>
>>> X() == ...
'hello'
i thinka == b work like that: ```py
def do_eq(obj1: object, obj2: object) -> object:
cls1 = obj1.class
cls2 = obj2.class
if issubclass(cls1, cls2):
t = cls2.__eq__(obj2, obj1)
if t is not NotImplemented:
return t
t = cls1.__eq__(obj1, obj2)
if t is not NotImplemented:
return t
return False
else:
t = cls1.__eq__(obj1, obj2)
if t is not NotImplemented:
return t
t = cls2.__eq__(obj2, obj1)
if t is not NotImplemented:
return t
return False
if both aren't implemented, it raises NotImplementedError
lean walrus
>>> class X:
... def __eq__(self, obj: object) -> bool:
... return NotImplemented
...
>>> X() == X()
False
oh huh
lean walrus
>>> class X:
... def __eq__(self, obj: object) -> bool:
... return NotImplemented
...
>>> class Y:
... def __eq__(self, obj: object) -> bool:
... return NotImplemented
...
>>> X() == Y()
False
>>> X().__eq__(X())
NotImplemented
>>> X().__eq__(Y())
NotImplemented
i want to create enum class with two (or more) orthogonal properties
for example, my enum instances can be either red or green and either round or square
how to do it easily?
import enum
class SomeEnum(enum.?):
?
e = SomeEnum(...)
# it is either red or green
assert e.is_red ^ e.is_green
# it is either round or square
assert e.is_round ^ e.is_square
the cube root of something is equivalent to raising it to the 1/3rd power, does that sound right?
nvm
haughty mountain
i want to create enum class with two (or more) orthogonal properties
for example...
two enums in one class?
i.e. a product type, that is a product of a color and shape enum
lean walrus
yes
i can make 4 enum entries and make properties for color and shape:
class X(enum.Enum):
red_round = 1
red_square = 2
green_round = 3
green_square = 4
@property
def is_red(self) -> bool:
return self in {X.red_round, X.red_square}
@property
def is_green(self) -> bool:
return not self.is_red
@property
def is_square(self) -> bool:
return self in {X.red_square, X.green_square}
@property
def is_round(self) -> bool:
return not self.is_square
but it is not pythonic
and in my case i need 5 values: 2*2 for two different properties + 1 special case
half lotus
Which part specifically
fiery cosmos
i understand up to like the cube root of something is equal to something^1/3 power
and using identity two you can further change that from lgn^1/3 = 1/3lgn
which by the way in this case lg is log base 2???
once they start trying to replace n with some m expression im lost
half lotus
Yeah lg has a base of 2
fiery cosmos
i think there is another important part here:
he's using this example to show his manipulations of m and n
i just get lost between the example and the actual expression we're trying to solve, too much going on
half lotus
Right they're trying to manipulate it so it's in the form of the master theorem
fiery cosmos
well there is the example expression and then the actual expression
If I let m = lg n, then I also have n = 2m by Identity 3, and
n1/3 = 2m/3 by the rule that (xy)z = xyz.
how does he go about m=lgn therefore n=2m
thats the bit i don't get
half lotus
It uses identity 3
fiery cosmos
oh i know
i've rewritten them as lgn=m and lg2^x=x
but looking at that its not intuitive what he did
if anything i think it'd be m = 2^n
but he's saying its n=2^m
half lotus
m = lg(n) = lg(2^m). If you look at the identity, it's x = lg(2^x). Notice how they are pretty similar, it's just that there is a substitution for 2^x. Like I can say let n = 2^x, thus x = lg(n) = lg(2^x). Now just replace x with m and you basically have the first thing I wrote.
More simply, lg(2^x) = lg(n) if n = 2^x.
And we know lg(2^x) = x by the identity, thus lg(n) must also equal x
fiery cosmos
ok. i'm not following, should i give up on doing graduate lvl algorithms?
fiery cosmos
ok i just feel like if i don't understand these things than there is no way i do well
it just all runs together there are too many lg's and x's and n's
half lotus
ok i just feel like if i don't understand these things than there is no way i do...
Well yes, it is important to understand. But not understanding something means you need to learn it, not that you should give up.
fiery cosmos
well yes its just that it is beyond unintuitive to me. i wouldn't inherently know to do any of these manipulations
half lotus
It's not inherent at first. You practice and get better.
fiery cosmos
how to obfuscate and compile with pyarmor?
half lotus
how to obfuscate and compile with pyarmor?
Wrong channel. See #❓｜how-to-get-help
Anyway, let me try again. Maybe it will help if I provide the identity using the same variable names as the example. The identity is lg(2^m) = m. All I did was take the identity and replace x with m. Does that make sense so far?
half lotus
In the example, they start off by saying let m = lg(n). Now you have two equations:
lg(2^m) = m # the identity
lg(n) = m # what we just introduced
So you see they are pretty similar. We can derive that 2^m = n from this
half lotus
Yeah which is fine cause in this context we're not dealing with imaginary numbers.
half lotus
So what I did was ```
lg(2^x) = x # take identity 3
lg(2^m) = m # rewrite it in terms of m to make it clearer
lg(n) = m # write the new equation introduced
And at this point the relationship should be clear
fiery cosmos
yes it is so long as you can just cancel a lg from both sides
half lotus
I don't think about it that way, but sure I suppose? I think of it more like, if I say lg(x) = 1, and lg(y) = 1, then x must equal y. We know this because lg is a function, and that means each input is associated with exactly one output.
So the only way 2 inputs can have the same output, is if those 2 inputs are in fact the same input
fiery cosmos
ok fair enough. i typically don't write the parenthesis because it further confuses me, but maybe its helpful to remember than lg is in fact a function
they could alternatively be equivalent inputs
half lotus
Well yes that is what I mean by "same"
fiery cosmos
right ok
ok so i can see where he derived n=2^m
i can use latex if you tell me how
oh nvm you're using this format
so how do we get to n^1/3 = 2^m/3?
wait let me try first
half lotus
Sure go for it
half lotus
Because we just established that n = 2^m, we can perform that substitution here n^(1/3) = (2^m)^(1/3)
And the rule it cites at the end shows that is equivalent to 2^(m * 1/3). m * 1/3 is just m/3 trivially
fiery cosmos
why would we be interested in raising to the 1/3 power because of the 1/3lgn?
half lotus
We're interested because we started with the cubed root of n which is equivalent to n^(1/3) we're just trying to rewrite this in terms of m instead.
fiery cosmos
right i got 1/3lgn from here:
ok so that takes us to here:
so now he defines a new function S()
with the objective of getting rid of the 2^something expressions
half lotus
Do you have questions about that substitution?
fiery cosmos
working on it
and by working on it i mean rewriting it on paper 😂
yeah im not really following
half lotus
Which step did you get lost at?
fiery cosmos
so far we got to T(2^m) = 3T(2^m/3)+1
now let 2^somevalue be expressed as some other function S()
define a new relation S(somevalue) = T(2^somevalue)
how can you say that some function S() = T(2^somevalue) and sub for both when T(2^m) and 3T(2^m/3) contain different expressions they are being raised to?
half lotus
Because somevalue is a variable, so it can take a different value each time the function is called
fiery cosmos
😵💫 wat
half lotus
S(m) = T(2^m), and S(m/3) = T(2^(m/3))
Like the general relationship is S(x) = T(2^x).
let x = m
Thus S(x) = S(m) = T(2^m)
let x = m/3
Thus
S(x) = S(m/3) = T(2^(m/3))
ohh i see. its bc S() is a function
half lotus
Correct
fiery cosmos
still very confusing
half lotus
S is a function, and so is T
fiery cosmos
i wish i had 100 of these docs to practice on
thank you so much for your time!!!
i don't super follow but im going to continue practicing
thanks again
half lotus
You're welcome
fiery cosmos
oh one last thing
after deriving all that they reapply the new format to understanding it given the master theorem, and there is an epsilon value for which they give no context. any idea what epsilon is??
context:
half lotus
The epsilon is part of case 1 of the master theorem
I remember you asked about this before
This is what you showed from your book https://cdn.discordapp.com/attachments/650401909852864553/984522089409159178/IMG_2611.jpg
See how case 1 has an epsilon
In this case, f(n) = 1, so we must find some epsilon that satisfies 1 = f(n) = O(...) (not gonna write the whole thing out)
fiery cosmos
ok thank you
"I’m using m instead of n to remember that we have a substitution to do later on."
what gives
half lotus
Remember near the start you let m = lg(n).
If you look at the last paragraph here, they account for that substitution when calculating the final value #algos-and-data-structs message
fiery cosmos
why does m^log_3*3-1 = m^0?
half lotus
because log_3^3 = 1, so you get m^(1 - 1) = m^0
half lotus
Oops I typed that wrong. I meant log_3(3)
Yeah this is why I like to use parenthesis for log. the subtraction happens after the log
half lotus
Yes. Not that they made a mistake; just the notation may not be clear.
half lotus
If there are no parenthesis it's meant to be interpreted as the minus being outside. The parenthesis would just make that explicit.
fiery cosmos
ok so we did this to prove that the asymptotic complexity of T(n) = 3T(3√n) + 1 is equal to theta(lgn)
is that it? will expressions with cube roots always have runtime complexity of some logarithm expression?
half lotus
Not necessarily. The a = 3 and f(n) = 1 also affect it.
half lotus
You're welcome
haughty mountain
yes it is so long as you can just cancel a lg from both sides
it's not cancelling, you're exponentiating both sides
brazen fern
hey guys whats your favorite thing to do with a csv or dataframe?
i'm short on ideas here
covert stirrup
can someone please explain to me why this is happening?
it works on my own laptop
but when its on leet
it messes up on 14
num = 14
def func(num):
i = -1
l = []
while i <num/2:
i = i + 1
t = i * i
l.append(t)
low = 0
high = len(l)
while low <= high:
mid = low + (high-low)//2
if l[mid] == num:
return 'true'
elif l[mid] < num:
low = mid +1
else:
high = mid - 1
return 'false'
print(func(num))
compared to
class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
i = -1
l = []
while i <num/2:
i = i + 1
t = i * i
l.append(t)
low = 0
high = len(l)
while low <= high:
mid = low + (high-low)//2
if l[mid] == num:
return 'true'
elif l[mid] < num:
low = mid +1
else:
high = mid - 1
return 'false'
they probably want return True return False
aka actual bools (though read the spec to be sure)
covert stirrup
wait what?
covert stirrup
wait what it is still supposed to return false?
fiery cosmos
return 'false' -> return False
covert stirrup
this thing is saying memory limit exceeded at 2000105819
how in tf is this supposed to even be possible
with this huge number
am i making this more difficult than it has to be
frail sun
If I have a lot of np.where/selects to make conditionals on a data frame, am I better off putting them in an excel file of sorts ? Then loading it in using a dictionary?
haughty mountain
this thing is saying memory limit exceeded at 2000105819
it's almost like there are nicer ways to do this 😉
if you just want to make your solution work, just generate squares while i*i <= n
i < n/2 is pretty pointless as a bound
and still there are better approaches, consider ||binary search||
actually, you do binary search, but why do it on the list?
you don't need the list at all
you use your list only to find...the square of the number, which you could just compute
zenith wasp
I'm trying to understand how numpy.dot works, but I'm struggling to understand this one:
If a is an N-D array and b is an M-D array (where M>=2), it is a sum product over the last axis of a and the second-to-last axis of b:
dot(a, b)[i,j,k,m] = sum(a[i,j,:] * b[k,:,m])
For example, the one before was easier to express:
If a is an N-D array and b is a 1-D array, it is a sum product over the last axis of a and b.
would be ```
items = map (0 until a.shape[a.lastAxisIndex]) to { axisIndex ->
viewOverAxis = a.view(axisIndex, axis = a.lastAxisIndex) // get a slice ofaover axis a.lastAxisIndex at position axisIndex
yield viewOverAxis * b[axisIndex] // b[axisIndex] is guaranteed to be a scalar
}
fold (items) to { acc, slice ->
yield acc + slice
}
I thought the other one would be as easy but it isn't
unborn meadow
Should fib(0) be equal to 0, or 1?
I see references saying the first Fibonacci element is 0 and others say that it is 1
shut breach
there's no real answer to that, it's arbitrary
haughty mountain
I'm trying to understand how numpy.dot works, but I'm struggling to understand t...
It's a bit weird to have dot products like that for higher dimensions. I think it's an extension of the 2d matrix multiplication
zenith wasp
I mean this is the docs straight from numpy
haughty mountain
the 1d case is kinda special, you basically interpret as a n x 1 column vector
zenith wasp
an (A, B, C, D) array dot (D, E, F, G) array gives an array with resulting shape (A, B, C, E, F, G) and I have no clue how I'd implement it like that
haughty mountain
wouldn't (A, B, C, X) dot (D, E, X, F) produce shape (A, B, C, D, E, F)?
err, let me correct the duplicate D...
maybe that's better
@zenith wasp I think you could think of fixating the value of dimensions A, B, D, E and then do a regular matrix multiplication (dot) of the (C, X) (X, F) submatrices
(or whatever the terminology is for a 2d slice of a tensor...)
zenith wasp
numpy treats a dot product on those arrays differently though
haughty mountain
does it?
zenith wasp
the matrix multiplication gives shape (2, 3, 1) while the dot product gives (2, 3, 1, 1)
zenith wasp
wouldn't (A, B, C, X) dot (D, E, X, F) produce shape (A, B, C, D, E, F)?
yeah sorry my mistake there
haughty mountain
idk what their matrix mult is defined as, the thing I described would be in terms of the regular 2d matrix mult which should be well defined
or at least less arbitrary than nd matrix mults
zenith wasp
I think their matrix multiplication does redundant dimension stripping (e,g, trailing size 1 dims stripped to just a single dim) but I don't know if that's true
and even then I wouldn't know how to really implement that
nvm, looks like I was wrong
haughty mountain
in any case, for their dot on my example from before you have something with shape (A, B) x (D, E) that contains matrices with shape (C, X) x (X, F)
you dot multiply all those 2d matrices and get loads of (C, F) matrices
something like that at least
zenith wasp
hmm, do you think you could put it into pseudocode like the previous example I posted with an N-D array and a 1-D array?
because I'm not sure I understand
haughty mountain
I guess their definition in terms of 1d dot products
dot(a, b)[i,j,k,m] = sum(a[i,j,:] * b[k,:,m])
```is easier. My thing was more how to see things as matrix multiplicationshape-wise that's (A, B, X) (C, X, D) -> (A, B, C, D)
where X are the dimensions you do the 1d scalar product along
(fixed the X positions)
the reason for those dimensions (last dim of a, second to last of b) being the Xs is to match regular matrix mult
at this point, starting to look at einsum might be interesting, it's based on einstein summation which is used for tensors in math
zenith wasp
I guess their definition in terms of 1d dot products
```
dot(a, b)[i,j,k,m] = su...
yeah I don't understand that one in the slightest sadly 
does that mean I need to iterate over all 4 remaining dims and multiply all of them or what
also how does that result in an (i,j,k,m) array if it's doing multiplication instead of matrix multiplication
gleaming bough
hello how can i search (not sequentally) in a heap?
haughty mountain
yeah I don't understand that one in the slightest sadly <:Ehehe:7717821481682207...
for all valid i, j, k, m, do a dot product in the remaining dimensions
zenith wasp
and how would I do an N-dimensional dot product?
haughty mountain
a[i, j, :] is a vector, a[k, :, m] is another vector of the same length
haughty mountain
and how would I do an N-dimensional dot product?
it's a 1d dot product
haughty mountain
and how would I do an N-dimensional dot product?
what their thing says is that the output of dot(a, b) at position (i, j, k, m) is this 1d dot product
sum(a[i,j,:] * b[k,:,m])
or
sum(a[i,j,x] * b[k,x,m] for x in range(N))
```if that's more familiar, let N be the size in those directionsso I need to loop over all possible combinations of ijkm
then calculate the dot product
haughty mountain
yes, which is yet another loop
zenith wasp
is there not a more efficient implementation than that?
haughty mountain
I mean, you need the first 4 loops for sure
since you at least need to populate the whole output
the question is whether you can get rid of part of the last O(n) cost, and you can to some extent, but the algorithms are not at all easy
zenith wasp
so for an 12D and 7D array I'll have an approximate performance of O(n^17)? Surely that can't be right
haughty mountain
more like O(n^18)
the output size alone is O(n^17)
you literally can't do better than O(n^17) for this problem
that would be linear time in the size of the output
and unless you do some fancy matrix multiplication algo like Strassen's algorithm you will get an extra O(n) factor
For reference Strassen's algorithm takes 2d matrix multiplication from O(n^3) to roughly O(n^2.8)
so a very minor improvement
haughty mountain
so for an 12D and 7D array I'll have an approximate performance of O(n^17)? Sure...
why doesn't that sound right?
zenith wasp
I feel like matrix math always has ways to do things more efficently than just looping over every element
haughty mountain
your output array is of size O(n^17)
you need to fill in all those elements at the very least
fiery cosmos
hi all,
not understanding the bit following "substituting into the recurrence yields"
i see how they get T(|n/2|)<=c|n/2|lg(|n/2|))
haughty mountain
from this?
if so, what part don't you understand?
this is the substitution made
and then the simplifications are in the original image
what part of it ends up being confusing?
fiery cosmos
I don’t understand the algebra and also there seems to be a /2 I thought should still be present that isn’t
If we’re substituting n/2 back into the recurrence for the first n following 2T I would think it’s (n/2)/2
haughty mountain
If we’re substituting n/2 back into the recurrence for the first n following 2T ...
we're not substituting n/2
we're substituting the expression for T(floor(n/2)) that we derived
like, in my image, literally replace the red thing, with the blue thing we know is greater
as for the algebra, in their inequalities
first step uses that floor(n/2)*2 <= n and floor(n/2) <= n/2
second step uses that log(a/b) = log(a) - log(b)
third step uses that log_2(2) = 1
last step just throws away the negative terms, and we get something bigger
the first few steps are there to isolate c n lg n which is the term we need to show what we want
fiery cosmos
as for the algebra, in their inequalities
first step uses that `floor(n/2)*2 <=...
where is the *2 coming from?
haughty mountain
where is the *2 coming from?
the 2 in front of the expression
fiery cosmos
floor(n/2)*2 <= n
where is this bit?
let me post the screenshot again
let me write it out
substituting into the recurrence yields:
2. <= cn lg(n/2) + n
3. = cnlgn - cnlog2 + n
4. = cnlgn - cn + n
5. <= cnlgn```what do they do between line 1 and 2?
opal oriole
what do they do between line 1 and 2?
It uses floor(n/2) <= n/2, then the 2 and n/2 that are multiplied become n.
fiery cosmos
sorry i'm not following
why does the expression after "yielding" in the screenshot transform into the one following "substituting into the recurrence yields"
why does the left hand side stay T(n) and the right we replace n with floor(n/2)
opal oriole
4.19 turns into it combined with the after yielding.
fiery cosmos
why do we not use T(floor(n/2)) on the left?
opal oriole
What is the left of 4.19?
fiery cosmos
T(n)
opal oriole
Yeah, which is what we want in the end.
fiery cosmos
then why do they including it in the expression just after "yielding"
that is why do they include that floor expression n/2
opal oriole
The expression after yielding is a separate expression (inequality, not just an expression).
fiery cosmos
thats the expression assuming that the bound holds for all positive m < n
the way im seeing it they add it in and then take it back out. i dont understand why
i also don't understand the algebra
opal oriole
They did not take it back out. It's two different expressions.
fiery cosmos
they effectively used everything on the right hand side of the expression after yielding and substituted it into 4.19
opal oriole
If I had something like x + 1 = 0 and y * 3 = 12. These are two different equations, and I can combine them however I want, e.g. x + 1 + y * 3 = 12 (added them).
They have two things, the after yielding, and 4.19. They then used them together, by substitution into 4.19.
fiery cosmos
i still don't understand how i would know to sub in the right hand things and not the left
it looks like they are subbing in floor(n/2) for all n on the right hand side and yet thats not it, what exactly are they doing
opal oriole
Because the left is what we want in the end. We want something like T(n) <= ....
fiery cosmos
right but why then would they write it in in the expression after yielding
opal oriole
Specifically c n lg n.
opal oriole
right but why then would they write it in in the expression after yielding
Write what in the expression after yielding?
fiery cosmos
they change the T(n) on the left to T(floor(n/2))
haughty mountain
this is the substitution made
do you understand what I'm marking here?
opal oriole
Because we want to get rid of the T(floor(n/2)) in 4.19.
So if we know something that we can substitute it with, we are all good to go.
(And that substitution is no longer a recurrence relation)
fiery cosmos
do you understand what I'm marking here?
no i'm sorry
haughty mountain
no i'm sorry
the line with T(n) = ... is the recurrence, right?
fiery cosmos
yep
haughty mountain
the thing on that line I marked red we have a bound for
i.e. the other thing I marked in red
red <= blue
so if we replace red in the recurrence with blue we get something larger
that's all the first step is
fiery cosmos
"we start by assuming that this bound holds for all positive m < n, in particular m = floor(n/2),"..
what is this about
haughty mountain
it's the assumption we make in the induction, that T(m) = O(m lg m) for m < n
fiery cosmos
sorry but in math i rarely know whats being asked, let alone what is reasonable to assume or not assume
haughty mountain
it's the assumption we make in the induction, that T(m) = O(m lg m) for m < n
(in other words that T(m) = c m lg m)
we could pick any m < n, it just so happens that m = floor(n/2) is useful
fiery cosmos
do you just look at whats inside T() and "use" that somehow?
haughty mountain
do you just look at whats inside T() and "use" that somehow?
where?
fiery cosmos
that must be where the floor(n/2) expression came from, the recurrence itself
still dont get "all positive m < n" assumption
like where that would even come from. if we're upper bounding the function wouldn't we be trying to find all positive m > n??
haughty mountain
that must be where the floor(n/2) expression came from, the recurrence itself
Not really, we can choose whatever m < n and the expression T(m) <= c * m lg m will be true per the assumption. We pick m = floor(n/2) because it turns out to be useful
haughty mountain
like where that would even come from. if we're upper bounding the function would...
this is a proof by induction
fiery cosmos
so you're telling me it has nothing to do with the fact that there is a floor(n/2) in the recurrence itself
haughty mountain
we assume something is true for values < n to prove it's true also for n
haughty mountain
so you're telling me it has nothing to do with the fact that there is a floor(n/...
it has something to do with it, we pick that particular m because it gives us a bound for T(floor(n/2))
fwiw, the bound is not a consequence of the recurrence, it's a consequence of our assumption
fiery cosmos
the logic is going in circles here. we pick T(x/n) because T(x/n) gives us a bound for T(x/n) is how im hearing it
maybe its more helpful if we work on another problem
haughty mountain
no, we pick m = floor(n/2) because that gives us a bound for T(floor(x/n))
T(floor(x/n)) is the annoying part of the recurrence we would love to get rid of
fiery cosmos
how do you distribute that 2 through the expression on the right side of the inequality
the T(floor(x/n) doesn't exist wrote that as an example
looks like it just cancels an n/2 to n
doesn't effect the lg for some reason
can i share my screen
lets work this one instead
which i also dont get 😵💫
i went over this yesterday so i am rereading everything
haughty mountain
I kinda want to stick with the first one. We have two independent things. We have the recurrence itself
T(n) = 2 T(floor(n/2)) + n
and we have the induction assumption we make, that for m < n, T(m) = O(m lg m), or in other words
T(m) <= c m lg m
for some constant c.
Those are the only two relations
fiery cosmos
does the m < n have to do with the floor notation?
is that why we're not doing m > n?
haughty mountain
are you familiar with induction in general?
fiery cosmos
all i understand is to prove an inductive statement you prove where something is true for n and then prove for n+1 or n-1 or the "next case"
i think we discussed this before and you or someone else had indicated that the base case and the inductive step can be done in any order?
but this is the "substitution method"
which i would think is separate from induction
oh nvm it says "inductive hypothesis"
haughty mountain
I think the book probably glosses over the base case here
fiery cosmos
ok
haughty mountain
we assume that something is true for m smaller than n, can we use that to prove it for n
fiery cosmos
btw i really need to go over the algebra if im ever going to get good at this
haughty mountain
this is just a slightly different flavor of "assume n-1 to prove n"
fiery cosmos
you mean if m = n-1?
haughty mountain
no? we assume the statement is true for all m < n
fiery cosmos
ok. but if we are finding an upper bound, wouldnt we instead be interested in m > n?
the problem statement is "let us determine an upper bound on the recurrence.."
fiery cosmos
right. meaning greater than
big O is like some function t(n) that is greater than f(n) if and only if there exist some constant that upper bound the function for all n greater than n nought
something like that
let me get the real def
haughty mountain
I kinda want to stick with the first one. We have two independent things. We hav...
it's basically that, I used it earlier here
fiery cosmos
O(g(n)) = f(n) iff there exist positive constants c and n_0 such that 0 <=f(n) <= cg(n) for all n >= n_0
i think it must have something to do with the floor symbol it doesnt make sense to have m < n for an upper bound
if anything if would have to be some function f(n) upper bounds my recurrence T(n) by being larger than it for the right constant and n
m < n sounds like a lower bound
do you see what i'm saying? that all sounds right to me but i obviously don't understand their premise with m<n
haughty mountain
I guess, let's start from the beginning. We have this recurrence we are interested in
we might have a feeling that T(n) should be in O(n lg n), but we would have to actually prove that
fiery cosmos
why might one have that feeling
why not lgn
nvm go ahead
the answer is that it can be whatever we want to guess but we have to then prove it
haughty mountain
right
fiery cosmos
would this be easier in voice?
fiery cosmos
right
haughty mountain
(for some large n)
fiery cosmos
sure
haughty mountain
we need to show that there is some c for which that thing holds
fiery cosmos
more importantly n
haughty mountain
well, we'll come to that
it's not obvious how one would prove this, but induction seems like a fun idea to try, this is where m < n comes in
our induction assumption will be that that inequality is true for values less than n
Now we want to show that the same c also works for m = n
The only two equations we have is the one at the top and the one at the bottom, we need to combine them somehow
So, what is it about the recurrence that makes it hard to analyze?
The fact that is is recursive
It would be great if we could get rid of that annoying T(floor(n/2)) on the right hand side
we are free to pick any m for the bottom equation, the annoying term in the recurrence is what motivates the choice m = floor(n/2)
floor(n/2) < n so it's a totally valid choice
so we now have two expressions, the recurrence
and the inequality where we chose a fitting value for m
Can we combine these?
like, if you follow/don't follow let me know
fiery cosmos
no i'm totally with you. i'll reply to the only bit i don't get
fiery cosmos
Now we want to show that **the same c** also works for m = n
this
thought we were still showing m<n
haughty mountain
I also forgot to share the new screenshot
haughty mountain
thought we were still showing m<n
we are not showing something for m < n
we are assuming something is true for m < n
with the hope of being able to show that it also holds for m = n
fiery cosmos
ok ok
haughty mountain
like, if I want to show that 1 + 2 + 3 + n = n*(n+1)/2, I can assume that it's true for small cases m < n and then prove that it also holds for m = n
and then show some base case, and everything follows
Ok, back to the question. Can we combine (1) and (2) to get something nice?
A huge motivation for us was to get rid of the annoying recursion
And we have a bound for the term that actually makes the recurrence recursive, so let's use it
the underlined part is the only thing that changes
fiery cosmos
yeah see this is where i get lost. i get that we are subbing into the original recurrence. i guess i can see why we use T(n) on the left side but not really. what gets me is the T(something) on the right completely goes away (but not the leading 2) and T(floor(n/2)) is replaced by some other term
haughty mountain
yeah see this is where i get lost. i get that we are subbing into the original r...
we know this, right?
fiery cosmos
yep
well actually i can see it now that you've underlined the bits that change
i just dont know how or why i would do any of these steps
haughty mountain
so what happens if I replace T(floor(n/2)) in the recurrence with what's on the right hand side?
we replace it with something larger, so the expression as a whole gets larger
hence the inequality shows up
like, if I have x = y and I know that y <= z, I also know that x <= z
that's really all that's going on there
haughty mountain
i just dont know how or why i would do any of these steps
well, induction proofs is kinda about making a decent educated guess and hope things work out
fiery cosmos
ok so what about the algebra
looks like that leading 2 is used to cancel the n/2 just after the c?
haughty mountain
we can't just cancel the 2
because it's inside the floor
but floor(n/2) <= n/2
fiery cosmos
can you show how to eval 2(c floor(n/2) * lg(floor(n/2)) + n?
haughty mountain
so we could substitute that in and again make the expression larger
fiery cosmos
no there is a 2 out front that needs distributed
opal oriole
i just dont know how or why i would do any of these steps
We need to prove T(n) <= c n lg n. We start from (1). So we need to get from (1) to the thing to be shown. So naturally we want T(n) on the left and something else on the right because that is what the end goal looks like.
haughty mountain
no there is a 2 out front that needs distributed
this partial step might help
opal oriole
We need to morph from the start to the end, and that involves doing this whole induction thing so we can get rid of the T(floor(n/2)) in (1) and in doing so hope to end up at the goal.
haughty mountain
we can substitute floor(n/2) with n/2 and it just makes things a bit larger (hence the <=)
now the 2s do cancel out
opal oriole
Like if I start with x + 3 = 0 and I want to prove that x = -3, naturally I know that I want x on the left side, and I know that I want to get rid of the 3 on the left side.
fiery cosmos
in the book its as if the leading 2 must also be distributed to the lg term as well
the 2 is out front of a parenthesis
haughty mountain
in the book its as if the leading 2 must also be distributed to the lg term as w...
wdym? 
fiery cosmos
can you show how to eval ```2(c floor(n/2) * lg(floor(n/2)) + n```?
it looks like this
haughty mountain
there is nothing to distribute there, it's all just multiplication
I think the extra () is just to highlight what I showed by underlining
that this is the thing we substituted
opal oriole
It's like 2xyz. If you had 2(x/2)yz you get xyz.
fiery cosmos
oh i guess we'd only distribute it if the terms inside the parenthesis were being added
theyre not, theyre being multiplied
opal oriole
Yeah.
fiery cosmos
dang. my algebra is real bad
haughty mountain
It's like `2xyz`. If you had `2(x/2)yz` you get `xyz`.
if you go through the extra step to get rid of the floors
opal oriole
Well it is distributed, but just 1 term, a bunch of things multiplied.
And yes there is the extra step of getting rid of the floor first.
haughty mountain
ok, I guess let's do the last few steps
basic logarithm properties: log(a/b) = log a - log b
let's use that
opal oriole
The floor of x is less than x, and since we are already dealing with an inequality, we can just do that, it's still valid.
haughty mountain
opal oriole
If y <= floor(x), then y <= x. Because x >= floor(x).
Made the right side bigger (maybe, could be equal), inequality still holds.
haughty mountain
our lg function is the base 2 logarithm so lg 2 is just 1
now, we actually need to constrain c here
if c >= 1 then -cn + n is negative, and we can do
which is the thing we actually wanted to prove
we needed to add a constraint on c but it was a reasonable constraint to add
haughty mountain
so, we have showed that the same value of c that worked for m < n also works for m = n
ah, they do add that constraint as well, cool
fiery cosmos
how would you ever look at all those symbols and know "what c must be"
i just have no mathematical reasoning skills
haughty mountain
in my math or their math on that page?
fiery cosmos
so, we have showed that the same value of c that worked for m < n also works for...
in what way did we show this?
i mean c must be 1 or greater or else the whole thing would be 0 yeah
but we dont know what n is
haughty mountain
in what way did we show this?
I mean, that is literally what we showed. We started with the induction assumption for m < n, and now we have showed that the same inequality also holds for m=n
we showed that T(n) <= c n lg n
with the same c we had before
fiery cosmos
i didn't know we showed 2 different things
haughty mountain
2 different things?
fiery cosmos
the induction assumption m<n and now the same inequality sounds like 2 different things
haughty mountain
the induction assumption is nothing that you show
you assume that it's true and see what the consequences are
fiery cosmos
i still dont get why we start with m < n when we're trying to show an upper bound
m < n and then that m = n sounds like two different cases
haughty mountain
the inequality in m < n has nothing to do with the upper bound we want to show
the upper bound has to do with the big O
you recall the definition of big O has an n0?
we want that our inequality is true for all values greater than n0
fiery cosmos
right
haughty mountain
that's why we want to show that the statement being true m < n implies that it's also true for m = n
because then it's also true for m = n+1
and n+2
and ...
now, the base case still remains
we need to pick some value of n0 and c that makes things work
fiery cosmos
why would something m < n being true imply its true for m = n ad greater? why doesnt it go in the other direction
haughty mountain
but when it works for the small cases it will continue to work, that is what we proved
fiery cosmos
like m < n implies its true for n = m-1, n=m-2, etc.
haughty mountain
like m < n implies its true for n = m-1, n=m-2, etc.
we assume that it's true for m < n
and we see what consequences that would have
the consequence in this case; if the things is true for m < n it's also true for m = n (and onwards)
haughty mountain
can you be more specific about "the other direction" in this case?
fiery cosmos
like m < n implies its true for n = m-1, n=m-2, etc.
this
haughty mountain
it's not really an implication
we assume it to be true for all those smaller values
fiery cosmos
i think there is something to do with the floor symbol im not understanding
fiery cosmos
for all positive m<n in particular for m=floor(n/2)
that notation means "the greatest integer <= x"
haughty mountain
yes, we can pick any value for m that is less than n and the inequality holds (per our assumption)
that particular value turns out to be useful to us
so we pick that
fiery cosmos
so in this case its m = the greatest integer <= n/2?
haughty mountain
yes, we pick that value of m
the value that makes it so that we have the same T expression that is used in the recurrence
fiery cosmos
alright im going to save my other questions for the next problem i'd like to review
maybe it'll be another day i know i've taken a lot of your time
haughty mountain
do you get their talk about the base case?
fiery cosmos
not at all
haughty mountain
so what we have shown so far is that if we have an ok value of c for small n, that value of c is also ok for larger n
but that if is important
maybe our assumption is just not true?
but we have two things we can fiddle with, we can pick whatever value we like for c
and we can pick the value of n0 in the definition of big O
it turns out that our assumption is not true for T(1)
fiery cosmos
yeah i'm not following that we've shown anything. i'm sorry i'm really not trying to waste your time
i just don't get this stuff
haughty mountain
you don't see the parallel between what we've done here and regular induction?
fiery cosmos
negative
again i'd like to save your brain power and expertise for a separate problem
maybe tomorrow if you are around
haughty mountain
this is literally just a slightly different flavor of induction
the only difference is that instead of assuming that something is true for m=n-1 and then showing that that implies m=n is also true
we assume that something is true for all m < n and use that to show that the thing is also true for m=n
we just assume some more stuff
fiery cosmos
right i just dont see how we showed that it was true for m < n or m = n
haughty mountain
we haven't shown that it's true for m < n
fiery cosmos
i mean, we chose something for m, and set it equal to something less than n, that is, floor(n/2)
but i don't get how we "showed" anything
haughty mountain
we started with this for m < n
right?
we then used that fact combined with the recurrence to show that this is also true
fiery cosmos
no, our m < n was = floor(n/2)
haughty mountain
we are free to use any value of m that is less than n
fiery cosmos
we set m = floor(n/2)
haughty mountain
because it happens to be useful
like, we assume that the statement is true for a huge number of values of m
all values < n
but not all values of m are that useful to us
it happens that floor(n/2) is useful because if gives us T(floor(n/2)) <= something
the same T(floor(n/2)) that annoys us in the recurrence
we could have picked whatever value of m, we assumed the statement to be true for all m < n
the overall scheme of the induction is the same, make use of the fact that something holds for m < n to show something for m = n
then you show some base case and everything follows
fiery cosmos
why didn't we try to show something was true for m > n?
is it bc its recursive (getting smaller)?
do recursions always grow smaller?
sigh
haughty mountain
it's not growing smaller though
we show stuff about larger values of m
than what we assumed to be true for
fiery cosmos
🤦♂️
haughty mountain
take the simple example of 1 + 3 + 5 + ... + n = n^2
we can assume it's true for m = n - 1
i.e.
1 + 3 + 5 + ... + (n - 1) = (n-1)^2
some rewriting later
1 + 3 + 5 + ... + (n - 1) = (n-1)^2
1 + 3 + 5 + ... + (n - 1) = n^2 - 2*n + 1
1 + 3 + 5 + ... + (n - 1) + (2*n - 1) = n^2
err, wait
I need to have an odd number
fiery cosmos
this example is nowhere close to correct though. 7+5+3+1 is nowhere near 49
haughty mountain
yeah, I put the wrong assumption
fiery cosmos
what is the assumption
haughty mountain
or well, the wrong formula I wanted to show
I think this is the one
1 + 3 + 5 + ... + (2*n - 1) = n^2
the sum of odd numbers is a square
fiery cosmos
wait can we try mine
to prove something is true or not true
lets try to prove that 1+3+5+...+n = n^2-6
wait sry
1+2+3+...+n = (n^2)-6
haughty mountain
that's not true
haughty mountain
sure, but you won't be able to prove the induction step
fiery cosmos
wat
isn't that what all this is about
if it doesn't work for something so simple how would we ever apply it to functions
oh wait the substitution method is only for recurrences 🤦♂️
fiery cosmos
1+2+3+...+n = (n^2)-6
this is a recurrence?
haughty mountain
the sum of the first n integers can be written as a recurrence
fiery cosmos
well it doesn't work for 5, but now im seeing proving it doesnt work for large n isnt the same problem bc our problem was about finding an asymptotic bound, not proving a simple expression evaluates true or not
haughty mountain
it's basically the same thing
agile sundial
that's the point of induction. if you prove it for n - 1, you can assume it's true for n
after you do that, you make n the new n - 1, and so on. that way, you've proved it for all n
haughty mountain
we just want to show that if the thing holds for small values (m<n) it's true for larger ones, in particular m=n
I managed to mess up the induction for the sum of odd numbers being a square 😭
fiery cosmos
the induction thing works for like say a loop where things are incrementing by 1, but i dont understand why it would work for any problem. why would n-1 imply that something is true for n? doesn't make snese
sense
haughty mountain
the induction thing works for like say a loop where things are incrementing by 1...
it doesn't in general
agile sundial
the induction thing works for like say a loop where things are incrementing by 1...
you prove that it works for n, assuming that n - 1 is true
haughty mountain
something being true for small numbers doesn't automatically mean it's true for larger ones
fiery cosmos
why would one assume n-1 equates to true
agile sundial
why would one assume n-1 equates to true
that's the second step of induction. the first step is to show that it works for some base case, usually n=0 or n=1
haughty mountain
would you ever do n+1
if I show that the statement being true for n-1 implies it's true for n, it will also be true for n+1
the n-1 to n stuff is to show I can show something for the next step
but n is arbitrary
agile sundial
maybe we should do an example?
fiery cosmos
pls
agile sundial
an easier one :P @haughty mountain
fiery cosmos
or we could work the other problem i have
where we use the master theorum to determine the asymptotic complexity of a recurrence
it involves 2 substitutions
maybe a simpler example would be better?
agile sundial
so, we want to prove that 1 + 2 + 3 + ... + n = n (n + 1) / 2
fiery cosmos
alright let me try first
can i just input 2 values like 5 and 6 or do i have to use expressions like n and n+1
haughty mountain
can i just input 2 values like 5 and 6 or do i have to use expressions like n an...
that's the point, we show it for an arbitrary n
fiery cosmos
so i'll need to use m and m+1?
agile sundial
if you use 5 and 6, you've shown that it works for 5 and 6, not for all n
haughty mountain
we want to show that we can jump one step up
agile sundial
for any n that you pick
fiery cosmos
so i'll need to use m and m+1?
?
haughty mountain
you can assume it's true for m-1 and show that implies that it's true for m
or m and m+1
whatever works
just two numbers after each other
fiery cosmos
well thats what i was on about with 5 and 6 but i dont know how to do it for n and n+1
agile sundial
it's just some algebra, what do you have so far?
oh. a key point with induction is that you need to use the inductive hypothesis (when you assume the statement is true for n) in your proof of n + 1
fiery cosmos
somethingonleftside = (n^2 + n)/2
agile sundial
ok, have you shown that it's true for a base case?
fiery cosmos
no i tried plugging in (n+1) and get n+1 = n^2+3n+3/2
im not capturing the left hand side properly
agile sundial
you're not going to be able to do the second step without the first step
fiery cosmos
well for n=1 its trivial
agile sundial
sure, you have
1 = 1(1 + 1) / 2 = 1
```which worksnow, you assume that
1 + 2 + 3 + ... + n = n (n + 1) / 2
```(because you just checked that it works for `n=1`)
and you need to prove that
```py
1 + 2 + 3 + ... + n + n + 1 = (n + 1) ((n + 1) + 1) / 2
we just plugged n + 1 in wherever there was an n in our last equation
after we verify that the base case works, we can assume our formula works
haughty mountain
spoilered calculations
agile sundial
since we assume our formula works, it should work with the next number as well, n + 1
very fancy
fiery cosmos
i get n=1 😢
i plugged in n+1 for n and got n=1, which i don't even know what that means
let me share my work
where did i go wrong?
fiery cosmos
well thats disheartening
fiery cosmos
```n + n+1 = (n+1)((n+1)+1))/2```?
this line
opal oriole
Not sure what you are doing with that line.
fiery cosmos
we're proving our n+1 case
fiery cosmos
now, you assume that
```py
1 + 2 + 3 + ... + n = n (n + 1) / 2
```(because you j...
as shown here
opal oriole
The left side is missing the 1 + 2 + 3 + ... +
And you don't plug in n+1, you add it to both sides of the equation.
fiery cosmos
right i wasn't sure how to capture that
fiery cosmos
we just plugged `n + 1` in wherever there was an `n` in our last equation
but this?
opal oriole
We assume it's true for 1 + 2 + 3 + ... + (n - 1) = (n-1)((n-1)+1)/2.
Then we need to get to the n case from n-1.
fiery cosmos
i'm just trying to do what the others are telling me how can i be goofing it up
i copied verbatum what public wrote
opal oriole
If we can get from the n-1 case to the n case, we have shown that we can reach the next rung.
fiery cosmos
ok
opal oriole
So how do you transform your starting point (the n-1 case) into the end point (the n case)?
What is the n-1 case first of all?
haughty mountain
you can start with whatever arbitrary thing
opal oriole
If you start at the n case, then from the POV of the n+1 case, it is the n-1 case. Same thing.
haughty mountain
you can assume that the statement is true for n + 738291 and show it for n + 738292 if you want to
the point is just to show it for the thing after it
fiery cosmos
how are you supposed to capture the 1+2+3+4.. part of the ...+n expression
agile sundial
you use the formula that you assumed works
haughty mountain
opal oriole
You assume that the rung you are currently on is not broken, then show that you can reach the next one.
fiery cosmos
that doesn't explain how you would know which rungs are beneath you
in order to add them together
add their values together that is
opal oriole
Well, we know the first rung is 1. The second is 1 + 2, the third is 1 + 2 + 3, etc.
fiery cosmos
correct
opal oriole
So the n-th rung is?
fiery cosmos
so n = 3 is not the same thing as 3+2+1
agile sundial
it is the same
opal oriole
n is the rung number.
fiery cosmos
they dont evaluate to the same value
opal oriole
n is how many terms.
agile sundial
they do though. 3(3 + 1)/2 = 1 + 2 + 3
fiery cosmos
wat
opal oriole
With n=3, we have 1 + 2 + 3, we can rewrite that as 1 + 2 + n.
haughty mountain
wait, why the rewrite?
haughty mountain
they dont evaluate to the same value
3(3 + 1)/2 = 3*4/2 = 6
1 + 2 + 3 = 6
^
fiery cosmos
so how do we capture whats on the left? none of these explanations has captured that
opal oriole
What do you mean by capture?
fiery cosmos
n=3 is not the same as n=3+2+1
agile sundial
so how do we capture whats on the left? none of these explanations has captured ...
by using the formula that you assume to be true
agile sundial
n=3 is not the same as n=3+2+1
we're not saying n=3 + 2 + 1
fiery cosmos
then youre not capturing the left hand side
agile sundial
wdym by "capturing"
fiery cosmos
you're not evaluating that expression
agile sundial
the left hand side is
1 + 2 + 3 + ... + n, right?
fiery cosmos
right so you cannot just set n equal to some thing n
agile sundial
why?
fiery cosmos
it must be n + n-1 + n-2 + n-3 or something
you cannot simply say some summation of numbers in the range 1...n = n.
haughty mountain
we didn't
fiery cosmos
you do if you ignore the summation and set it equal to n or n-1
haughty mountain
who did that and when?
we thing that
1 + 2 + ... + n = n*(n+1)/2
```that formula for the next value would be
1 + 2 + ... + n + n+1 = (n+1)*(n+2)/2
(or equivalently we could pick n-1 and n like I did in my spoilered image)
fiery cosmos
i don't understand how i'm not being clear. you're effectively saying that n and 1+2+3+n are the same thing
haughty mountain
i don't understand how i'm not being clear. you're effectively saying that n and...
where?
agile sundial
who said that
fiery cosmos
when you run the proof, you drop all the numbers and just evaluate n + (n+1) right?
haughty mountain
no?
fiery cosmos
thats what we've been doing
agile sundial
i think you're misunderstanding something
fiery cosmos
what else is new
opal oriole
Don't drop the 1 + 2 + 3 + ... at any point and try again.
haughty mountain
like, here is the argument I did
fiery cosmos
we have to, otherwise we'd have to add every number on the way to arbitrarily large n, destroying the point of proof by inductin
haughty mountain
I don't drop anything anywhere
opal oriole
You can just skip the second equation then. You have the n-1 case.
fiery cosmos
now, you assume that
```py
1 + 2 + 3 + ... + n = n (n + 1) / 2
```(because you j...
i understood this
haughty mountain
using m for one equation doesn't change the argument at all
agile sundial
i understood this
well, ok. can you prove that the second statement is true then?
fiery cosmos
You can just skip the second equation then. You have the n-1 case.
wouldn't it have to be ...+n+(n-1)?
haughty mountain
... + (n-2) + (n-1)
opal oriole
wouldn't it have to be ...+n+(n-1)?
Let n=3, then we have 1 + 2 + 3 = 1 + 2 + n = 1 + (n - 1) + n = (n - 2) + (n - 1) + n.
opal oriole
wouldn't it have to be ...+n+(n-1)?
We would not have n in the n-1 case.
We only go up to n-1.
haughty mountain
no
agile sundial
no, you dropped the 1 + 2 + 3 + ... + n
opal oriole
You are missing the left side summation.
Don't drop it, ever, as previously written.
fiery cosmos
so how do you express it
agile sundial
1 + 2 + 3 + ... + n works pretty well
agile sundial
we don't have to evaluate it
opal oriole
1 + 2 + 3 + ... + (n+1) or 1 + 2 + 3 + ... + n + (n + 1).
etc.
(We have n in the n+1 case)
In the left version it's just in the ...
fiery cosmos
ok how about 1+2+3..+n+1 = n+1((n+1)+1))/2
agile sundial
that looks right. actually no, your order of operations will be messed up on the right side. you need some more parentheses
haughty mountain
you don't
agile sundial
well, you need to do "math", but you don't need to evaluate what that value is
fiery cosmos
how then would i prove if the = is true
agile sundial
you use the equation from the previous step, that you assumed to be true
remember, when you assumed that 1 + 2 + 3 + ... + n = n(n + 1)/2?
agile sundial
we assumed that:
1 + 2 + 3 + ... + n = n(n + 1)/2
we need to prove:
1 + 2 + 3 + ... + n + n + 1 = (n+1)(n+2)/2
``` can you see how there's considerable overlap between the two statements? you need to use the first equation to help you prove the second equationWhat happens if you add n+1 to both sides of the n case (it's an equation, so you add to both sides)? What does the left side look like? What does the right side look like?
fiery cosmos
1 + 2 + 3 + ... + n + n + 1 = (n+1)(n+2)/2
although then we're adding n+1 to left and subbing it in on the right which i dont get
haughty mountain
no, just add n+1 to both sides
opal oriole
although then we're adding n+1 to left and subbing it in on the right which i do...
Just add to both sides yourself, see what happens.
haughty mountain
i.e. work from this
1 + 2 + 3 + ... + n + (n + 1) = n(n+1)/2 + (n+1)
i get (n^2+2n+1)/2
agile sundial
how?
fiery cosmos
i distribute the n through (n+1) then add the n+1 to the numerator putting it all over 2
agile sundial
so you did
n(n+1)/2 + n+1
(n^2 + 1)/2 + n+1
(n^2+2n+1)/2
```?how does the second n+1 get divided by 2
agile sundial
sorry, i assumed
haughty mountain
n(n + 1)/2 + (n + 1)
= n(n + 1)/2 + 2(n + 1)/2
= (n(n + 1) + 2(n + 1))/2
= (n + 2)(n + 1)/2
You multiply the right term by 2/2 (fancy form of 1).
haughty mountain
fiery cosmos
why
agile sundial
where does that 2 come in
you've essentially done n+1 = (n+1)/2, which doesn't make sense. adding the 2 on the top makes it work, because you've multiplied the top and bottom by 2, not just the bottom
opal oriole
Because we want both terms to be divided by 2 so we can combine them.
opal oriole
Like how do you do: 3 + 1/2?
3 * 2/2 + 1/2, still same thing, multiplied by 1.
= 6/2 + 1/2 = 7/2.
Combined two terms into one.
(Common divisor (2))
fiery cosmos
so you get (n^2 + 3n +2) / 2?
haughty mountain
in this case expanding things isn't too helpful
when you are at this step, how many (n+1)s do you have on top?
(n(n + 1) + 2(n + 1))/2
2
haughty mountain
n on the left. and 2 on the right
haughty mountain
so n+2 total
fiery cosmos
idk i factored it back out to ((n+1)(n+2))/2
agile sundial
exactly
fiery cosmos
ok so now what
haughty mountain
factoring stuff is an inherently harder problem, especially when you come to higher degree polymonials
being lazy is good
agile sundial
ok so now what
you're done
fiery cosmos
wat
agile sundial
you've shown that the formula works when you go to n+1
fiery cosmos
we didn't show anything
haughty mountain
we showed that we can get from the n case to the n+1 case
opal oriole
If you let m=n+1, and then replace all the n+1 in your thing with m, it becomes more obvious.
fiery cosmos
we just got somethingonleft = ((n+1)*(n+2))/2
haughty mountain
that something on the left is the sum of the n+1 first numbers
which is the thing we were interested in
agile sundial
or 1+2+3+...+n+n+1
fiery cosmos
but since we didnt evaluate them we'll never know if the = sign evaluated to True
agile sundial
we don't need to evaluate them
opal oriole
We know the = is true because to get here we did not do any invalid algebra.
fiery cosmos
you can't have an equation without knowing the value of the one side
haughty mountain
if the n case is true then the n+1 case is true
opal oriole
Each step is valid, so the end is valid.
fiery cosmos
otherwise everything is equal to everything else and nothing else
haughty mountain
we would still need to show a base case, e.g. n=0
agile sundial
you can't have an equation without knowing the value of the one side
sure you can
haughty mountain
but when we have the 0 case we know it holds for 1 because of the thing we proves
and if being true for 1 means it's true for 2
opal oriole
sure you can
Say I have the equation y=x, I don't know either value, but if at any point i'm given x, say 3, then I know y must be 3, or the other way around.
haughty mountain
and so on
fiery cosmos
how did y'all avoid my expansion and then factoring back out earlier? the algebra?
agile sundial
we just didn't distribute the n
haughty mountain
how did y'all avoid my expansion and then factoring back out earlier? the algebr...
you mean this?
haughty mountain
I have n apples and another 2 apples, I have n+2 apples in total
kinda
replace apple with (n+1)
fiery cosmos
huh
opal oriole
3x + 5x = 8x, nx + 5x = (n + 5)x.
fiery cosmos
😵💫
agile sundial
we didn't show anything
the thing we proved is that
if the n case is true, then the n+1 case is true. this by itself is useless, but we also have the fact that it works for the base case. because we know that, we know it works for all cases after the base case
fiery cosmos
i still don't feel that we proved anything
especially since we didn't evaluate the left side
opal oriole
i still don't feel that we proved anything
We showed we could get from the n case to the n+1 case without breaking any rules.
The = was always valid at each step.
fiery cosmos
we don't know if its valid, as we never evaluated the left side
it could evaluate to False
vocal gorge
mathematical induction works like this, roughly speaking:
- you have some statement
S(i), whereiis an index. You want to prove that it's true for allistarting from, say, 0. - you prove S(0) is true
- you prove that if, for some
i,S(i)is true, thenS(i+1)is true. - therefore, S(0) being true implies S(1) and so on, so S(i) is true for all i>=0.
agile sundial
we don't know if its valid, as we never evaluated the left side
why not? we don't need to know n + n = 2n, what the value of n is, we know it's true
fiery cosmos
and the right we just got (((n+1)*(n+2))/2)
fiery cosmos
which doesn't mean anything on its own
opal oriole
If I have x + 3 = 6, and I assume that is valid, then if I do x = 3 (sub 3 from both sides), because I did not break any rules, that is also valid. The = still holds.
So I proved x = 3.
fiery cosmos
we have n red boxes on the left side, and 2 red boxes on the right side
sure but how does that equate to n+1 and n+2
haughty mountain
sure but how does that equate to n+1 and n+2
we have n+2 red boxes, the red box is n+1
(n+2)*(n+1)
fiery cosmos
mathematical induction works like this, roughly speaking:
- you have some statem...
right this makes sense with a for loop when you're incrementing by 1, not for any case
agile sundial
we know for a fact that n + n = 2n, we don't need to know what n is, we already know it's true
fiery cosmos
go on
agile sundial
similarly, we assumed 1+2+3+...+n=n(n+1)/2, right?
fiery cosmos
we assumed it was true, we never proved anything
agile sundial
sure
but if we assume that it's true
as long as what we do to the equation is valid mathematically, then the equation still holds
vocal gorge
right this makes sense with a for loop when you're incrementing by 1, not for an...
Why not?
haughty mountain
we **assumed** it was true, we never proved anything
yes, we proved that if it's true for n then it's also true for n+1
we know the statement is true for something like n=0
agile sundial
that's what our base case is for, the first step of induction
haughty mountain
so we can apply the induction we proved
because we know that the statement for n=0 is true, so the statement for n=1 is also true
fiery cosmos
you could show it works for one, and then n+1, but then n would have to be 1 (the base case) and you'd simply be working on 2
agile sundial
because we know that n=1 is true, so n=2 is also true
because we know that n=2 is true, so n=3 is also true
because we know that n=3 is true, so n=4 is also true
fiery cosmos
that doesn't make sense
agile sundial
why not? we showed that if it's true for n then it's also true for n+1
fiery cosmos
apply to it anything tangible and non-math and it breaks down
why then should it be true or physical systems?
agile sundial
well, who cares. we're applying it to math
haughty mountain
what breaks down?
fiery cosmos
no, we're applying it to computer science, where physical RAM has limits
i cant think of one concept where it does make sense actually
haughty mountain
computer science is a lot more abstract than that
fiery cosmos
its still governed by physical laws
agile sundial
theoretical computer science doesn't really have physical limits like that
fiery cosmos
every cpu is made of atoms that follow nature
haughty mountain
cs is a branch of math, if anything
opal oriole
Theoretical computer science is a branch of math.
^
They just don't want it to be that in Uni because they don't want it counting towards a math major for credits.
fiery cosmos
lmao
agile sundial
that doesn't make sense
why not? we showed that it if it works for n, then it must work for n + 1. we showed that it works for n=0, so it must work for n=0+1
opal oriole
*Despite science being in the name. It's not really, more math-like. Though in some cases there is science involved in the parts that deal with real machines. It's a bit of a mess.
haughty mountain
but you have noticed an important thing, actually adding all the things is annoying, we can be clever and avoid doing that
fiery cosmos
i don't think we can, otherwise we're not actually proving the expression we set out to evaluate the trueness of
haughty mountain
much like how we used induction to remove the annoying recurrence in the original problem we discussed
fiery cosmos
not to mention, im left with some terms n+1 and n+2 / 2, with no context
let me eval and see if it works for some small n
haughty mountain
do you understand the ladder analogy?
fiery cosmos
no
i don't understand how to evaluate our new expression
lets say im evaluating 5
do i add the four as well, do i skip?
haughty mountain
what we showed is that you can go from any arbitrary step on the ladder to the step after
fiery cosmos
left hand is ...+ n+1
we didn't show that, because we never showed what the left hand side equates to
it was some nonsense notation
vocal gorge
Do you agree that, if A=>B and B=>C and A is true, then C is true?
fiery cosmos
as i said before, to evaluate it should have been n + n-1 + n-2 + n-3.. etc
sure
but unless you evaluate that its meaningless
agile sundial
reptile pls
opal oriole
LaTeX does not work in this channel 😦
vocal gorge
Well, do you agree that if A0 is true, and A0 => A1, and A1 => A2, and in general Ai => A{i+1} for any i>=0, then An is true for any n>=0?
bot might just be down, again
agile sundial
no, we don't have perms
opal oriole
I tried before and said it was not in this channel, only data science and one other I think.
vocal gorge
ah, right
haughty mountain
bot might just be down, again
right, we proved Ai => A{i+1}
and yes, induction kinda feels like cheating
you made an educated guess on some formula
you use induction to show that it works
but in the end you probably didn't get any nice insight other than that the formula is true
fiery cosmos
i cant think of one situation where it makes sense outside of math
are there any good examples?
haughty mountain
like, there are physical analogues of induction at work, sure
vocal gorge
nothing is truly outside of math :p
fiery cosmos
~~nothing is truly outside of math~~ :p
thats what i was saying before. everything is governed by physical laws
haughty mountain
place a long sequence of dominoes such that each domino will tip over another one, tip over the first one and all of them fall
only in mathematical world you have infinite dominoes
and the tipping goes on forever towards infinity
fiery cosmos
if the first domino is n, there is no n-1 domino
similarly no n+1 domino at the end
haughty mountain
I mean, infinities aren't exactly common in the physical world
vocal gorge
I mean, mathematical induction doesn't require infinities? you are welcome to only induct up to n :p
fiery cosmos
infinites do come into play when talking about ever larger n though
so i see why we're discussing them
the induction thing i think is a made up circumstance in math to make the formulas "make sense"
though i dont see how they show anything
as in our proof we worked before
when we never evaluated the left hand side of the equation and the right was some arbitrary mathematical terms involving n
haughty mountain
when we never evaluated the left hand side of the equation and the right was som...
they aren't arbitrary
it is the formula for the sum of the first n integers
if it was anything else the induction proof wouldn't have worked
fiery cosmos
how would you know its true if we never evaluated the left hand side? the left could be anything
haughty mountain
we evaluated the left hand side for something like n=0
our argument then says that implies it's true for n=1 as well
fiery cosmos
zero isnt a real case
haughty mountain
what does that even mean?
vocal gorge
...use one then? but also, sure zero is a real case, why wouldn't it be