« first day (1668 days earlier)      last day (3348 days later) » 
00:00 - 17:0017:00 - 18:0018:00 - 23:0023:00 - 00:00

evinda
evinda
11:00 PM
@Axoren Do we maybe pick a specific c or do we show that it holds that $g(n)+O(f(n))=\Theta(f(n))$ ?
 
Axoren
Axoren
Sorry, I'm thinking. My family is in the house so things are a little hectic.
 
A Beautiful Mind
A Beautiful Mind
One cannot think in a chat room.
 
Axoren
Axoren
I do it out here, behind a keyboard :P
 
A Beautiful Mind
A Beautiful Mind
One thinks in his mind.
 
Axoren
Axoren
@evinda So, from what it looks like, little-o is a much stronger upper bound.
That every constant $c$, rather than just one constant $c$ satisfies it for some $n_0$.
If something is $o(f(n))$, then it should also be $O(f(n))$, if I'm not mistaken.
 
evinda
evinda
11:10 PM
@Axoren You mean that it suffices to show that $f(n)+O(f(n))=\Theta(f(n))$ ?
 
Axoren
Axoren
@evinda I believe so.
Ahh, wait.
 
evinda
evinda
@Axoren Nice... and how could we explain it formally?
 
Axoren
Axoren
There's a slight problem with this logic.
Actually, there might not be.
But it's much easier if we go back to using simply the little-o
What does being little-o tell us?
It tells us that a function is both less than $cf(n)$ and $(c+d)f(n)$
 
evinda
evinda
We set $g(n)=o(f(n))$.That means that $\forall c>0, \exists n_0 \in \mathbb{N}$ such that $\forall n \geq n_0: g(n)< cf(n)$. @Axoren
 
Axoren
Axoren
When you add $f(n)$ to that function, do know a lower bound for it?
 
evinda
evinda
11:15 PM
So you mean that we do not take a specific c?
 
Axoren
Axoren
We don't need a specific $c$
Not for big-theta
 
evinda
evinda
So you mean that we say the following:
We set $g(n)=o(f(n))$.That means that $\forall c>0, \exists n_0 \in \mathbb{N}$ such that $\forall n \geq n_0: 0\ leq g(n)< cf(n)$.
So: $f(n) \leq f(n)+g(n) \leq cf(n)+f(n)=(c+1)f(n), \forall n \geq n_0$.
? @Axoren
 
Axoren
Axoren
Yup.
On second thought, you could probably have done this just using $o(f(x)) \implies O(f(x))$
But why squander stronger statements?
 
evinda
evinda
So you mean that I should do it as above? @Axoren
 
Axoren
Axoren
Yes.
 
evinda
evinda
11:22 PM
@Axoren But then don't we have to pick a specif value for c, since according to the definition:
$f(n)=\Theta(g(n))$ iff $\exists c_1, c_2>0, n_0 \in \mathbb{N}$ such that $\forall n \geq n_0$: $c_1 g(n) \leq f(n) \leq c_2 g(n)$ ?
Or don't we have to mention two specific c_1, c_2?
 
Axoren
Axoren
The specific value is any value that satisfied o(f(x))
Which is specifically every value.
So you can just pick any value greater than 1.
You are sure that the lower bound's $c$ is 1 because you added it yourself.
Sorry, I've got to take a short break. An toddler is being mischievous so I have to pretend to be a nursery-tale monster.
 
evinda
evinda
@Axoren Above I wrote an equality, but it should be an inequality.
We set $g(n)=o(f(n))$.That means that $\forall c>0, \exists n_0 \in \mathbb{N}$ such that $\forall n \geq n_0: 0 \leq g(n)< cf(n)$.
So: $f(n) \leq f(n)+g(n) < cf(n)+f(n)=(c+1)f(n), \forall n \geq n_0$.
Right? So do we say that $f(n) \leq f(n)+g(n) < cf(n)+f(n)=(c+1)f(n) \Rightarrow f(n) \leq f(n)+g(n) \leq (c+1)f(n), \forall n \geq n_0$

So picking $c_1=1, c_2=c+1$ we see that $f(n)+g(n)=\Theta(f(n)) \Leftrightarrow f(n)+o(g(n))=\Theta(f(n))$
 
Axoren
Axoren
@evinda That works.
 
evinda
evinda
@Axoren Nice, thank you!!! Do you have a little brother? :D
 
Axoren
Axoren
Nephew.
They're leaving shortly
 
Maximilian
Maximilian
11:36 PM
Hello
I need help with this problem
\frac{Cos\Theta+1}{Tan^2\Theta}=\frac{Cos\Theta}{Sec\Theta-1}
Is that showing up for you? The LaTeX editor shows it correctly but I'm only seeing the text for the one I posted:P
 
Mike Miller
Mike Miller
look at LaTeX in chat on the right
 
Maximilian
Maximilian
I think it hates me:P
 
Mike Miller
Mike Miller
oh
 
Maximilian
Maximilian
I have it working for others equations, and an LaTeX editor shows it correctly
 
Mike Miller
Mike Miller
you forgot to add your dollar signs
$x^2$
 
Maximilian
Maximilian
11:47 PM
$\frac{Cos\Theta+1}{Tan^2\Theta}=\frac{Cos\Theta}{Sec\Theta-1}$
There it goes!
Ok, well thats the equation I need help on, I have to make sure it an identity
When trying to simplify $\frac{cos\Theta}{sec\Theta-1}$ I get $-cos\Theta$
I think a bug just went inside a whole of my laptop:O
 
00:00 - 17:0017:00 - 18:0018:00 - 23:0023:00 - 00:00

« first day (1668 days earlier)      last day (3348 days later) »