Book: Algorithms in C from Robert SedgewickSearching online, the only thing I find is this excerpt from Wikipedia:"In more complicated usage, O ( ⋅ ) can appear in different places in an equation, even several times on each side.The meaning of such statements is as follows: for any functions which satisfy each O ( ⋅ ) on the left side, there are some functions satisfying each O ( ⋅ ) on the right side, such that substituting all these functions into the equation makes the two sides equal"
>>170253131. Start from AOPS Prealgebra2. Just get a Pro Max San Sama OpenAI Claude subscription.
>>17025317Can you do it?
For example, in the fourth part:let h1 = f - g = O(h(n))then:f = g + h1 and h1 = O(h(n)),therefore:f = g + O(h) holds.Do you think it's okay?
>>17025313Just apply the definition of O(f(N)), most of these are just finding the constant M in the inequality for the right hand side.
>>17025313f(N) -> O(f(N))proof: it's trivialcO(f(N) -> O(f(N))proof: left as exercise to the reader
1 and 2 are trivial from the definition.3 follows from one and two4 might as well be trivial too but f = f - g + g = O(h) + g5 follows from 36 follows from 2 and 3.btw this is a blatant homework thread, you could have easily just asked AI instead of wasting my time.
>>170254041 and 2 come from the axioms used to construct most modern computers and arent trivial
>>17025313Get LLM to create you a complete Algorithm ebook. With improvements for each chapter from AI.
>>17025704>1 and 2 come from the axioms used to construct most modern computers and arent trivialExplain.
>>17025712its non trivial to explain it bro
>>17025313for cO(f(N)) = O(c f(N)) to be a non-trivial statement we would need the exact definition the book uses for these expressions because depending on how you introduce any of this it is trivial.
Why is the Wikipedo definition for big O so awkward? Why a domain D when NO other definition (and no practical application I know of) needs anything other than an interval? Why not just[eqn]g(n) = O(f(n)) \iff \limsup_{x\to x_0} \frac{|g(n)|}{f(n)} < \infty[/eqn]
>>17026365ugh, [math]n\to\infty[/math], for real analysis sometimes it makes sense to have x0 where x0 is usually infinity
>∞
>/sci/ is incapable of applying a definition to simple examples How low the mighty have fallen
>>17026374I would unironically love to do it but I am not going to do it from a definition other than the book's, that would be cheating. But frankly I would say it suffices to prove a select few things.[eqn]f \in O(f)[/eqn]Trivially true because [math] \limsup_{n\to\infty} \frac{|f|}{|f|} = 1 < \infty [/math][eqn]O(c f) = c O(f) ~ (c \neq 0)[/eqn]is true because if c is nonzero then c and 1/c are finite and whatever the limit is without c is just scaled by a finite factor.The fourth is true because conventionally it is defined to be eqvilanent.Next,[eqn]a\in O(f), b\in O(g)\Rightarrow\limsup\frac{|ab|}{|fg|} \leq \limsup\frac{|a|}{|f|}\limsup\frac{|b|}{|g|}<\infty[/eqn]which implies [math]O(f)O(g)\subseteq O(fg)[/math] which is a valid transformation to make whenever you can replace a set by a superset without loss of generality.Finally,[eqn]h\in O(f) \wedge f\in O(g) \Rightarrow \limsup \frac{|h|}{|g|} = \limsup \frac{|hf|}{|gf|} \leq \limsup \frac{|h|}{|f|} \limsup \frac{|f|}{|g|} < \infty \Rightarrow O(f)\subseteq O(g)[/eqn]
>>17025313wtf is this even supposed to teach you?
>>17025313You should probably read Knuth's Concrete Math before attempting any book on algorithms.
>>17026388isn't O(cf) = cO(f) true for c = 0 as well?
>>17026480Not quite, O(0) contains more than the null function, but the thing I left unsaid that was the main reason I excluded c=0 is that [math] O(cf) = O(f) [/math] is only true for nonzero c.
>>17026505>O(0) contains more than the null functionwhat else does it contain?
>>17026508Every function that is 0 eventually, for example the step function [math]\Theta(-x)[/math]. Most of the caveats are a consequence of us including functions that aren't monotonic, which are usually the most relevant for algorithms and such.
>>17026524Oooooh shit good point. Nice.
