5
Your expression is
$$ E = \frac{cn^2}{\log \frac{n(n+1)}{2}}$$
where $c$ is some constant. The simple upper bound for $E$ is
$$ E\le c n^2$$
which implies that $\mathcal{O}(n^2)$. For a better bound
$$E = \frac{cn^2}{\log \frac{n(n+1)}{2}} = \frac{cn^2}{ 2 \log n + \log n - \log 2 } $$
Now it is an easy verification that $E$ is $\mathcal{O}(\frac{n^...
2
$O(n^c \log n)$ is above $O(n^c)$ but below $O(n^{c+\varepsilon})$ for any $\varepsilon > 0$. This is true for any $c \geq 0$, including $c < 1$.
For example, $n^{0.5} \log n$ is not in $O(n^{0.5})$ but is in $O(n^{0.500001})$.
This is one of the reasons for the invention of the "soft O" notation $\tilde{O}(n^c)$, defined as the union of $O(n^c (\log ...
1
The function $n^5 + n^7$ is big-$Ω$ of both. However, it is little-$\omega$ of $n^5$.
It happens that $n^5 + n^7 \in \Theta(n^7)$. These asymptotic-notations only describe the behavior of the function $f(n) = n^5 + n^7$ for large $n$, aka "for all $n > \textrm{some value}$". The function is a polynomial function, and the highest-degree term determines ...
1
Assuming the model of computation is RAM(Random Access Machine). Which means the cost of addition, multiplication,division etc is constant. Now your program is
int j = 0;
for (int i = 1; i <= n; i *= 2) {
j = j + n * 2;
}
Inside the loop, you are doing addition, multiplication, comparison etc which takes constant time. Let $k$ denotes the number of ...
1
If $f(x) = O(x^n)$ then $f(x)^m = O(x^{nm})$. Indeed, $f(x) = O(x^n)$ means that $f(x) \leq Cx^n$ for some $C>0$. Therefore $f(x)^m \leq C^mx^{nm}$, and so $f(x)^m = O(x^{nm})$.
On the other hand, it is not true that $(g(x) + h(x))^m = g(x)^m + O(h(x)^m)$. For example, suppose that $g(x) = 2$ and $h(x) = 1$. Then it is not the case that $3^m = 2^m + O(1)$...
Only top voted, non community-wiki answers of a minimum length are eligible
