All Questions
37
questions
0
votes
0
answers
43
views
Question On Function Growth rate
Assume we have the grow rate of $log(n^{2n})$, $log(n!)$, $n(log(n))^3$, $n(2^n)$, $n^{(1.5)}$,$n^{(log(log(n)))}$,$\sqrt{2^{log(n)}}$,$2^{(\sqrt{log(n)})}$,$2^{(log\sqrt{n})}$,$2^{(2n)}$, $(log(n))!$ ...
- 1
1
vote
3
answers
238
views
What actually growth of a function represents?
I am going through the book Discrete Mathematics by Kenneth Rosen. In chapter 3, there is a topic "The Growth of Functions" and then Big-O Notation. I am really unable to understand what ...
- 4,470
0
votes
3
answers
131
views
How to show properly $ 10n^4 + 3n^3 -n \in O(n^4)$?
Given:
$$ 10n^4 + 3n^3 -n \in O(n^4)$$
So i do understand Big O and what it does. I am however not quite if my approach for the solution is correct, so anyone who could help me out or show me an ...
- 331
0
votes
2
answers
65
views
one doubt on big oh notation
I see an example that $f(n)=O(n)$ and $\sum_{i=1}^nf_i(n)=O(n^2) $ in which $f_i$ is a function from natural to natural number.
I ran into a challenge, that above notation is differ from the
...
- 1
0
votes
1
answer
46
views
maybe crazy question on asymptotic notation
I see two time complexity.
$O ( m (\log m + \log n))$ and $O(m \log m \log n)$.
Is it correct that according to logarithm rules tell these are equals A) from asymptotic view and B) from math point of ...
- 27
1
vote
4
answers
459
views
$ \sqrt n \log \sqrt n$ is lower than $n$ ?!
I see an example in asymptotic notation that not very sensible for me.
what is the intuitive idea to understand $ \sqrt n \log \sqrt n$ is lower than $n$ in concept of asymptotic view?
- 27
1
vote
1
answer
57
views
How little o can verify for one example?
I have following facts:
$n^2log_2n+n^2$ = $o(n^3)$
how I can understand this is true fact? I'm not rain into a homework question, any intuitively idea to quickly find or doing by math?
1
vote
1
answer
207
views
two asymptotic comparison on sparse graph and misunderstanding point
I read in my notes:
if we use Dijkstra $|V|$ times ($|V|$ number of vertexes) for finding all pairs shortest paths in graph $G$, We get time complexity for Dijkstra algorithm as $O(VE+ V^2 log V)$ and ...
- 63
2
votes
1
answer
28
views
asymptotic statement and one example
how I can logically understand this is false ($c$ is constant):
$ \frac{n!}{c} \leq 2^n$
why it was false for large value from asymptotic notation concept? ( i see this is true for some $n < n_0$ ...
0
votes
1
answer
220
views
Some big-theta and big-omega notation question
Let $f : \mathbb{N} \rightarrow \mathbb{R}$ be the function $f ( n ) = n ^ { 2 } + \sqrt { n }$. Determine whether the following statement is true or false, providing a proof for your answer.
$ f(n) =...
- 39
0
votes
0
answers
23
views
Asymptotic relation between $n^2 (n-2\lfloor \frac{n}{2} \rfloor)$ and $2\lfloor \frac{n}{2} \rfloor$
What is asymptotic relation between $n^2 (n-2\lfloor \frac{n}{2} \rfloor)$ and $2\lfloor \frac{n}{2} \rfloor$?
My attempt: let $\lfloor \frac{n}{2} \rfloor = n$. Then the equation comes down to $n^3 ...
- 1,250
0
votes
2
answers
272
views
How to prove $n^6$ is big-O but not big-Omega of the function $(1.001)^n$
I know that, $n^c \in \mathcal{O}(2^n)$ for any constant $c$.
However, I don't know how to prove, or whether it is correct that, $n^c \in \mathcal{O}(1.001)^n$ for any constant $c$. Does anyone has ...
- 1,250
0
votes
1
answer
154
views
Time complexity of an iterative function related to bits
I am wondering about correct answer to this task from a test earlier today:
A function Pow which calculates $y = a^k$ is given, where $k$ is an
integer of ...
- 1,392
0
votes
1
answer
29
views
Prove whether $f(n)$ is $O$, $o$, $\Omega$, $\omega$ or $\Theta$ of $g(n)$.
$f(n) = e^{n} \ln(n)$,
$g(n) = 2^{n} \log(n)$
log can be assumed to be base $2$.
Alright so I put this in the form $f(n) / g(n)$ and then used L'Hôpital's rule giving me
$$ \frac { \dfrac{e^n}{n} +...
- 667
0
votes
0
answers
25
views
Is this solution correct? Prove whether $f(n)$ is $O$, $o$, $\Omega$, $\omega$ or $\Theta$ of $g(n)$
$f(n) = n + (\log n)^{2}$, $g(n) = n + \log(n^{2})$.
log is assumed to be base 2
So I differentiated each of the functions
$f(n)' = 1 + 2(\log n)$
$g(n)' = 1 + (2/n\ln(2))$
and then finding the ...
- 667