Can't seem to find the lower bound for this function
0
Been reading about algorithms. I am trying to find the lower and upper bounds for the function f(n). not very familiar with mathjax so i used mathtype. how do i proceed with the lower bound. especially the denominator.
also, is the upper bound $24n$ the tightest possible bound ?
algorithms asymptotics upper-lower-bounds
edited Nov 27 '18 at 16:00
Arthur
110k7105186
asked Nov 27 '18 at 16:00
Awaisome
102
add a comment |
0
Been reading about algorithms. I am trying to find the lower and upper bounds for the function f(n). not very familiar with mathjax so i used mathtype. how do i proceed with the lower bound. especially the denominator.
also, is the upper bound $24n$ the tightest possible bound ?
algorithms asymptotics upper-lower-bounds
edited Nov 27 '18 at 16:00
Arthur
110k7105186
asked Nov 27 '18 at 16:00
Awaisome
102
The best upper bound in the sense you are looking for, is $frac {19}{5}n+1.$
– user376343
Nov 27 '18 at 16:19
@user376343 i am looking for both bounds in the form $0<=c_1.g(n)<=f(n)<=c_2.g(n)$
– Awaisome
Nov 27 '18 at 17:17
add a comment |
0
0
0
Been reading about algorithms. I am trying to find the lower and upper bounds for the function f(n). not very familiar with mathjax so i used mathtype. how do i proceed with the lower bound. especially the denominator.
also, is the upper bound $24n$ the tightest possible bound ?
algorithms asymptotics upper-lower-bounds
edited Nov 27 '18 at 16:00
Arthur
110k7105186
asked Nov 27 '18 at 16:00
Awaisome
102
Been reading about algorithms. I am trying to find the lower and upper bounds for the function f(n). not very familiar with mathjax so i used mathtype. how do i proceed with the lower bound. especially the denominator.
also, is the upper bound $24n$ the tightest possible bound ?
algorithms asymptotics upper-lower-bounds
algorithms asymptotics upper-lower-bounds
edited Nov 27 '18 at 16:00
Arthur
110k7105186
asked Nov 27 '18 at 16:00
Awaisome
102
edited Nov 27 '18 at 16:00
Arthur
110k7105186
asked Nov 27 '18 at 16:00
Awaisome
102
edited Nov 27 '18 at 16:00
Arthur
110k7105186
edited Nov 27 '18 at 16:00
Arthur
110k7105186
edited Nov 27 '18 at 16:00
Arthur
110k7105186
110k7105186
asked Nov 27 '18 at 16:00
Awaisome
102
asked Nov 27 '18 at 16:00
Awaisome
102
asked Nov 27 '18 at 16:00
Awaisome
102
102
The best upper bound in the sense you are looking for, is $frac {19}{5}n+1.$
– user376343
Nov 27 '18 at 16:19
@user376343 i am looking for both bounds in the form $0<=c_1.g(n)<=f(n)<=c_2.g(n)$
– Awaisome
Nov 27 '18 at 17:17
add a comment |
The best upper bound in the sense you are looking for, is $frac {19}{5}n+1.$
– user376343
Nov 27 '18 at 16:19
@user376343 i am looking for both bounds in the form $0<=c_1.g(n)<=f(n)<=c_2.g(n)$
– Awaisome
Nov 27 '18 at 17:17
The best upper bound in the sense you are looking for, is $frac {19}{5}n+1.$
– user376343
Nov 27 '18 at 16:19
The best upper bound in the sense you are looking for, is $frac {19}{5}n+1.$
– user376343
Nov 27 '18 at 16:19
@user376343 i am looking for both bounds in the form $0<=c_1.g(n)<=f(n)<=c_2.g(n)$
– Awaisome
Nov 27 '18 at 17:17
@user376343 i am looking for both bounds in the form $0<=c_1.g(n)<=f(n)<=c_2.g(n)$
– Awaisome
Nov 27 '18 at 17:17
add a comment |
1 Answer
1
active
oldest
votes
1
An bound for $f$ is simply
$$
frac{19}{5}n le f(n)le frac{19}{5}n + 1
$$
for all $nge 1$. This follows from $0le 1-frac{1}{n}le 1$. Usually for the algorithm one just says that $f$ is in $O(n)$. So you could also take any estimate like $f(n)le 10^6n$ for all $nge 1$.
answered Nov 27 '18 at 16:37
Dietrich Burde
77.6k64386
i am looking for the form $c.g(n)$. also how do i got about finding the lower bound
– Awaisome
Nov 27 '18 at 17:18
just take $c=1$ and $g(n)=19n/5$.
– Dietrich Burde
Nov 27 '18 at 19:02
ok. but if $g(n)$ is not the same for both the bounds then we can't say $f(n)$ is $Theta(n)$ , right?
– Awaisome
Nov 28 '18 at 4:54
@Awaisome Have a look at this question, or this question etc. Have you tried to search yourself already?
– Dietrich Burde
Nov 28 '18 at 9:13
well i took hint from what you said above that $0le 1-1/nle 1$ and solved lower bound for $19n/5$. already had the upper bound $24n$. could you confirm if these are right? i mean i am fairly new to this stuff and i don't know for sure if i these are right, secondly as i asked above, if the $g(n)$ for both bounds come out to be different (like $c_1.logn^2le f(n)le c_2.n^3$), that means $f(n)$ is not in $Theta(n)$, right?
– Awaisome
Nov 28 '18 at 12:12
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3015941%2fcant-seem-to-find-the-lower-bound-for-this-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
1
An bound for $f$ is simply
$$
frac{19}{5}n le f(n)le frac{19}{5}n + 1
$$
for all $nge 1$. This follows from $0le 1-frac{1}{n}le 1$. Usually for the algorithm one just says that $f$ is in $O(n)$. So you could also take any estimate like $f(n)le 10^6n$ for all $nge 1$.
answered Nov 27 '18 at 16:37
Dietrich Burde
77.6k64386
i am looking for the form $c.g(n)$. also how do i got about finding the lower bound
– Awaisome
Nov 27 '18 at 17:18
just take $c=1$ and $g(n)=19n/5$.
– Dietrich Burde
Nov 27 '18 at 19:02
ok. but if $g(n)$ is not the same for both the bounds then we can't say $f(n)$ is $Theta(n)$ , right?
– Awaisome
Nov 28 '18 at 4:54
@Awaisome Have a look at this question, or this question etc. Have you tried to search yourself already?
– Dietrich Burde
Nov 28 '18 at 9:13
well i took hint from what you said above that $0le 1-1/nle 1$ and solved lower bound for $19n/5$. already had the upper bound $24n$. could you confirm if these are right? i mean i am fairly new to this stuff and i don't know for sure if i these are right, secondly as i asked above, if the $g(n)$ for both bounds come out to be different (like $c_1.logn^2le f(n)le c_2.n^3$), that means $f(n)$ is not in $Theta(n)$, right?
– Awaisome
Nov 28 '18 at 12:12
add a comment |
1
An bound for $f$ is simply
$$
frac{19}{5}n le f(n)le frac{19}{5}n + 1
$$
for all $nge 1$. This follows from $0le 1-frac{1}{n}le 1$. Usually for the algorithm one just says that $f$ is in $O(n)$. So you could also take any estimate like $f(n)le 10^6n$ for all $nge 1$.
answered Nov 27 '18 at 16:37
Dietrich Burde
77.6k64386
i am looking for the form $c.g(n)$. also how do i got about finding the lower bound
– Awaisome
Nov 27 '18 at 17:18
just take $c=1$ and $g(n)=19n/5$.
– Dietrich Burde
Nov 27 '18 at 19:02
ok. but if $g(n)$ is not the same for both the bounds then we can't say $f(n)$ is $Theta(n)$ , right?
– Awaisome
Nov 28 '18 at 4:54
@Awaisome Have a look at this question, or this question etc. Have you tried to search yourself already?
– Dietrich Burde
Nov 28 '18 at 9:13
well i took hint from what you said above that $0le 1-1/nle 1$ and solved lower bound for $19n/5$. already had the upper bound $24n$. could you confirm if these are right? i mean i am fairly new to this stuff and i don't know for sure if i these are right, secondly as i asked above, if the $g(n)$ for both bounds come out to be different (like $c_1.logn^2le f(n)le c_2.n^3$), that means $f(n)$ is not in $Theta(n)$, right?
– Awaisome
Nov 28 '18 at 12:12
add a comment |
1
1
1
An bound for $f$ is simply
$$
frac{19}{5}n le f(n)le frac{19}{5}n + 1
$$
for all $nge 1$. This follows from $0le 1-frac{1}{n}le 1$. Usually for the algorithm one just says that $f$ is in $O(n)$. So you could also take any estimate like $f(n)le 10^6n$ for all $nge 1$.
answered Nov 27 '18 at 16:37
Dietrich Burde
77.6k64386
An bound for $f$ is simply
$$
frac{19}{5}n le f(n)le frac{19}{5}n + 1
$$
for all $nge 1$. This follows from $0le 1-frac{1}{n}le 1$. Usually for the algorithm one just says that $f$ is in $O(n)$. So you could also take any estimate like $f(n)le 10^6n$ for all $nge 1$.
answered Nov 27 '18 at 16:37
Dietrich Burde
77.6k64386
edited Nov 27 '18 at 18:11
answered Nov 27 '18 at 16:37
Dietrich Burde
77.6k64386
answered Nov 27 '18 at 16:37
Dietrich Burde
77.6k64386
answered Nov 27 '18 at 16:37
Dietrich Burde
77.6k64386
77.6k64386
i am looking for the form $c.g(n)$. also how do i got about finding the lower bound
– Awaisome
Nov 27 '18 at 17:18
just take $c=1$ and $g(n)=19n/5$.
– Dietrich Burde
Nov 27 '18 at 19:02
ok. but if $g(n)$ is not the same for both the bounds then we can't say $f(n)$ is $Theta(n)$ , right?
– Awaisome
Nov 28 '18 at 4:54
@Awaisome Have a look at this question, or this question etc. Have you tried to search yourself already?
– Dietrich Burde
Nov 28 '18 at 9:13
well i took hint from what you said above that $0le 1-1/nle 1$ and solved lower bound for $19n/5$. already had the upper bound $24n$. could you confirm if these are right? i mean i am fairly new to this stuff and i don't know for sure if i these are right, secondly as i asked above, if the $g(n)$ for both bounds come out to be different (like $c_1.logn^2le f(n)le c_2.n^3$), that means $f(n)$ is not in $Theta(n)$, right?
– Awaisome
Nov 28 '18 at 12:12
add a comment |
i am looking for the form $c.g(n)$. also how do i got about finding the lower bound
– Awaisome
Nov 27 '18 at 17:18
just take $c=1$ and $g(n)=19n/5$.
– Dietrich Burde
Nov 27 '18 at 19:02
ok. but if $g(n)$ is not the same for both the bounds then we can't say $f(n)$ is $Theta(n)$ , right?
– Awaisome
Nov 28 '18 at 4:54
@Awaisome Have a look at this question, or this question etc. Have you tried to search yourself already?
– Dietrich Burde
Nov 28 '18 at 9:13
well i took hint from what you said above that $0le 1-1/nle 1$ and solved lower bound for $19n/5$. already had the upper bound $24n$. could you confirm if these are right? i mean i am fairly new to this stuff and i don't know for sure if i these are right, secondly as i asked above, if the $g(n)$ for both bounds come out to be different (like $c_1.logn^2le f(n)le c_2.n^3$), that means $f(n)$ is not in $Theta(n)$, right?
– Awaisome
Nov 28 '18 at 12:12
i am looking for the form $c.g(n)$. also how do i got about finding the lower bound
– Awaisome
Nov 27 '18 at 17:18
i am looking for the form $c.g(n)$. also how do i got about finding the lower bound
– Awaisome
Nov 27 '18 at 17:18
just take $c=1$ and $g(n)=19n/5$.
– Dietrich Burde
Nov 27 '18 at 19:02
just take $c=1$ and $g(n)=19n/5$.
– Dietrich Burde
Nov 27 '18 at 19:02
ok. but if $g(n)$ is not the same for both the bounds then we can't say $f(n)$ is $Theta(n)$ , right?
– Awaisome
Nov 28 '18 at 4:54
ok. but if $g(n)$ is not the same for both the bounds then we can't say $f(n)$ is $Theta(n)$ , right?
– Awaisome
Nov 28 '18 at 4:54
@Awaisome Have a look at this question, or this question etc. Have you tried to search yourself already?
– Dietrich Burde
Nov 28 '18 at 9:13
@Awaisome Have a look at this question, or this question etc. Have you tried to search yourself already?
– Dietrich Burde
Nov 28 '18 at 9:13
well i took hint from what you said above that $0le 1-1/nle 1$ and solved lower bound for $19n/5$. already had the upper bound $24n$. could you confirm if these are right? i mean i am fairly new to this stuff and i don't know for sure if i these are right, secondly as i asked above, if the $g(n)$ for both bounds come out to be different (like $c_1.logn^2le f(n)le c_2.n^3$), that means $f(n)$ is not in $Theta(n)$, right?
– Awaisome
Nov 28 '18 at 12:12
well i took hint from what you said above that $0le 1-1/nle 1$ and solved lower bound for $19n/5$. already had the upper bound $24n$. could you confirm if these are right? i mean i am fairly new to this stuff and i don't know for sure if i these are right, secondly as i asked above, if the $g(n)$ for both bounds come out to be different (like $c_1.logn^2le f(n)le c_2.n^3$), that means $f(n)$ is not in $Theta(n)$, right?
– Awaisome
Nov 28 '18 at 12:12
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3015941%2fcant-seem-to-find-the-lower-bound-for-this-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
The best upper bound in the sense you are looking for, is $frac {19}{5}n+1.$
– user376343
Nov 27 '18 at 16:19
@user376343 i am looking for both bounds in the form $0<=c_1.g(n)<=f(n)<=c_2.g(n)$
– Awaisome
Nov 27 '18 at 17:17