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