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 ?
Asked
Active
Viewed 478 times
0
-
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
1 Answers
1
An bound for $f$ is simply $$ \frac{19}{5}n \le f(n)\le \frac{19}{5}n + 1 $$ for all $n\ge 1$. This follows from $0\le 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 $n\ge 1$.
Dietrich Burde
- 130,978
-
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
-
-
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 04: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 09:13
-
well i took hint from what you said above that $0\le 1-1/n\le 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^2\le f(n)\le c_2.n^3$), that means $f(n)$ is not in $\Theta(n)$, right? – Awaisome Nov 28 '18 at 12:12