# Tag Info

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