How to prove NOT big omega?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I understand how to prove a function f(n) is $Omega(g(n))$ - just find a positive $c$ and $a$ such that $ cg(x)) leq f(x) $ for all $ x gt a$ - but I'm not sure how to begin a proof that says $f(n) not subseteq Omega (g(n))$.
The specific problem I'm working on is: $ f(n)=2^n, g(n)=2^n+1$ (trivial, I know)
proof-writing algorithms asymptotics
edited Aug 27 at 16:21
Alex
14k42032
asked Aug 27 at 16:12
user360431
111
add a comment |Â
up vote
1
down vote
favorite
I understand how to prove a function f(n) is $Omega(g(n))$ - just find a positive $c$ and $a$ such that $ cg(x)) leq f(x) $ for all $ x gt a$ - but I'm not sure how to begin a proof that says $f(n) not subseteq Omega (g(n))$.
The specific problem I'm working on is: $ f(n)=2^n, g(n)=2^n+1$ (trivial, I know)
proof-writing algorithms asymptotics
edited Aug 27 at 16:21
Alex
14k42032
asked Aug 27 at 16:12
user360431
111
You have to invert some quantifiers: you need to show that for every $c>0,a>0$ there exists $x>a$ such that $cg(x)>f(x)$. But to save you some time, let me tell you that this will not be possible for those $f,g$. So you may want to check your reference's definition of $f=Omega(g)$, because it might be the same as $g=o(f)$ (which would not be the definition that you gave here).
– Ian
Aug 27 at 16:21
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I understand how to prove a function f(n) is $Omega(g(n))$ - just find a positive $c$ and $a$ such that $ cg(x)) leq f(x) $ for all $ x gt a$ - but I'm not sure how to begin a proof that says $f(n) not subseteq Omega (g(n))$.
The specific problem I'm working on is: $ f(n)=2^n, g(n)=2^n+1$ (trivial, I know)
proof-writing algorithms asymptotics
edited Aug 27 at 16:21
Alex
14k42032
asked Aug 27 at 16:12
user360431
111
I understand how to prove a function f(n) is $Omega(g(n))$ - just find a positive $c$ and $a$ such that $ cg(x)) leq f(x) $ for all $ x gt a$ - but I'm not sure how to begin a proof that says $f(n) not subseteq Omega (g(n))$.
The specific problem I'm working on is: $ f(n)=2^n, g(n)=2^n+1$ (trivial, I know)
proof-writing algorithms asymptotics
edited Aug 27 at 16:21
Alex
14k42032
asked Aug 27 at 16:12
user360431
111
edited Aug 27 at 16:21
Alex
14k42032
edited Aug 27 at 16:21
Alex
14k42032
edited Aug 27 at 16:21
Alex
14k42032
14k42032
asked Aug 27 at 16:12
user360431
111
asked Aug 27 at 16:12
user360431
111
asked Aug 27 at 16:12
user360431
111
111
You have to invert some quantifiers: you need to show that for every $c>0,a>0$ there exists $x>a$ such that $cg(x)>f(x)$. But to save you some time, let me tell you that this will not be possible for those $f,g$. So you may want to check your reference's definition of $f=Omega(g)$, because it might be the same as $g=o(f)$ (which would not be the definition that you gave here).
– Ian
Aug 27 at 16:21
add a comment |Â
You have to invert some quantifiers: you need to show that for every $c>0,a>0$ there exists $x>a$ such that $cg(x)>f(x)$. But to save you some time, let me tell you that this will not be possible for those $f,g$. So you may want to check your reference's definition of $f=Omega(g)$, because it might be the same as $g=o(f)$ (which would not be the definition that you gave here).
– Ian
Aug 27 at 16:21
You have to invert some quantifiers: you need to show that for every $c>0,a>0$ there exists $x>a$ such that $cg(x)>f(x)$. But to save you some time, let me tell you that this will not be possible for those $f,g$. So you may want to check your reference's definition of $f=Omega(g)$, because it might be the same as $g=o(f)$ (which would not be the definition that you gave here).
– Ian
Aug 27 at 16:21
You have to invert some quantifiers: you need to show that for every $c>0,a>0$ there exists $x>a$ such that $cg(x)>f(x)$. But to save you some time, let me tell you that this will not be possible for those $f,g$. So you may want to check your reference's definition of $f=Omega(g)$, because it might be the same as $g=o(f)$ (which would not be the definition that you gave here).
– Ian
Aug 27 at 16:21
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
The inverse of the statement :
there exist $c$ and $a$ such that for all $x > a$ we have $f(x) geq c g(x)$
is that don't exist $c$ and $a$ satisfying those conditions, therefore every $c,a$ don't satisfy those conditions, therefore:
For all positive $c$ and $a$, we can find $x > a$ such that $f(x) < cg(x)$.
Thus, $f notin Omega(g)$ is defined by the above condition.
As it turns out, if $f(n) = 2^n$ and $g(n) = 2^n+1$ then we actually have $f(n) in Omega(g(n))$, since we may take the constants $a = 1$ and $c = frac 12$ in the given definition. So this was not the right example to take.
To illustrate a better example, take $f(n) equiv 1$ and $g(n) = n$. Then, given $c$ and $a$, we can certainly find $x > a$ such that $1 < cx$, by taking $x$ greater than the maximum of $a$ and $frac 1c$, so $f(n) notin Omega(g(n))$.
answered Aug 28 at 16:30
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
33.5k22870
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
The inverse of the statement :
there exist $c$ and $a$ such that for all $x > a$ we have $f(x) geq c g(x)$
is that don't exist $c$ and $a$ satisfying those conditions, therefore every $c,a$ don't satisfy those conditions, therefore:
For all positive $c$ and $a$, we can find $x > a$ such that $f(x) < cg(x)$.
Thus, $f notin Omega(g)$ is defined by the above condition.
As it turns out, if $f(n) = 2^n$ and $g(n) = 2^n+1$ then we actually have $f(n) in Omega(g(n))$, since we may take the constants $a = 1$ and $c = frac 12$ in the given definition. So this was not the right example to take.
To illustrate a better example, take $f(n) equiv 1$ and $g(n) = n$. Then, given $c$ and $a$, we can certainly find $x > a$ such that $1 < cx$, by taking $x$ greater than the maximum of $a$ and $frac 1c$, so $f(n) notin Omega(g(n))$.
answered Aug 28 at 16:30
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
33.5k22870
add a comment |Â
up vote
0
down vote
The inverse of the statement :
there exist $c$ and $a$ such that for all $x > a$ we have $f(x) geq c g(x)$
is that don't exist $c$ and $a$ satisfying those conditions, therefore every $c,a$ don't satisfy those conditions, therefore:
For all positive $c$ and $a$, we can find $x > a$ such that $f(x) < cg(x)$.
Thus, $f notin Omega(g)$ is defined by the above condition.
As it turns out, if $f(n) = 2^n$ and $g(n) = 2^n+1$ then we actually have $f(n) in Omega(g(n))$, since we may take the constants $a = 1$ and $c = frac 12$ in the given definition. So this was not the right example to take.
To illustrate a better example, take $f(n) equiv 1$ and $g(n) = n$. Then, given $c$ and $a$, we can certainly find $x > a$ such that $1 < cx$, by taking $x$ greater than the maximum of $a$ and $frac 1c$, so $f(n) notin Omega(g(n))$.
answered Aug 28 at 16:30
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
33.5k22870
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The inverse of the statement :
there exist $c$ and $a$ such that for all $x > a$ we have $f(x) geq c g(x)$
is that don't exist $c$ and $a$ satisfying those conditions, therefore every $c,a$ don't satisfy those conditions, therefore:
For all positive $c$ and $a$, we can find $x > a$ such that $f(x) < cg(x)$.
Thus, $f notin Omega(g)$ is defined by the above condition.
As it turns out, if $f(n) = 2^n$ and $g(n) = 2^n+1$ then we actually have $f(n) in Omega(g(n))$, since we may take the constants $a = 1$ and $c = frac 12$ in the given definition. So this was not the right example to take.
To illustrate a better example, take $f(n) equiv 1$ and $g(n) = n$. Then, given $c$ and $a$, we can certainly find $x > a$ such that $1 < cx$, by taking $x$ greater than the maximum of $a$ and $frac 1c$, so $f(n) notin Omega(g(n))$.
answered Aug 28 at 16:30
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
33.5k22870
The inverse of the statement :
there exist $c$ and $a$ such that for all $x > a$ we have $f(x) geq c g(x)$
is that don't exist $c$ and $a$ satisfying those conditions, therefore every $c,a$ don't satisfy those conditions, therefore:
For all positive $c$ and $a$, we can find $x > a$ such that $f(x) < cg(x)$.
Thus, $f notin Omega(g)$ is defined by the above condition.
As it turns out, if $f(n) = 2^n$ and $g(n) = 2^n+1$ then we actually have $f(n) in Omega(g(n))$, since we may take the constants $a = 1$ and $c = frac 12$ in the given definition. So this was not the right example to take.
To illustrate a better example, take $f(n) equiv 1$ and $g(n) = n$. Then, given $c$ and $a$, we can certainly find $x > a$ such that $1 < cx$, by taking $x$ greater than the maximum of $a$ and $frac 1c$, so $f(n) notin Omega(g(n))$.
answered Aug 28 at 16:30
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
33.5k22870
answered Aug 28 at 16:30
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
33.5k22870
answered Aug 28 at 16:30
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
33.5k22870
answered Aug 28 at 16:30
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
33.5k22870
33.5k22870
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2896353%2fhow-to-prove-not-big-omega%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
You have to invert some quantifiers: you need to show that for every $c>0,a>0$ there exists $x>a$ such that $cg(x)>f(x)$. But to save you some time, let me tell you that this will not be possible for those $f,g$. So you may want to check your reference's definition of $f=Omega(g)$, because it might be the same as $g=o(f)$ (which would not be the definition that you gave here).
– Ian
Aug 27 at 16:21