New answers tagged

1

Don't use the equals sign! $o(n \log_2 n)$ is the set of functions whose growth rate is strictly less than $n \log_2\,n$. So the proper expression is $f(n) \in o(n \log_2 n)$. Similarly, $O(n \log_2 n)$ is the set of functions whose growth rate is less than or equal to $n \log_2\,n$. The simple way to determine which expressions are true is to look at the ...


1

Asymptotic notation satisfies the following two useful properties: $$ \Theta(f(n)) + \Theta(g(n)) = \Theta(\max(f(n),g(n)) \\ \Theta(f(n)) \Theta(g(n)) = \Theta(f(n)g(n)) $$ Using these, you can determine that $f(n) = \Theta(4n^2\log^2 n)$. Now you can check each of 1.-5. individually, using the fact that $n^a\log^bn = O(n^c\log^dn)$ iff $a < c$ or $a=c$ ...


4

An obvious function is $$ f(n) = \begin{cases} n \log n & \text{if $n$ is even}, \\ 0 & \text{if $n$ is odd}. \end{cases} $$ It's in $O (n \log n)$, it's not in $o (n \log n)$ and not in $\Theta(n \log n)$. By the way: Every function in $\Theta(f(n)))$ is in $O(f(n))$, just take the larger constant from the $\Theta$ definition. And every function ...


1

What the definition is saying is: $f\in O(g)$ if there's a number $n_0$ such that $f(n)$ is less than some multiple of $g(n)$ (that's where the $c$ comes in) for all $n$ larger than $n_0$. In simple terms, it's saying that $f$ is eventually bounded by some fixed multiple of $g$. Big-O notation is essentially a simplification describing the ultimate rate of ...


1

$f(n)$ is not $O(n^2\log n)$ If we denote $f(n) = (n\log n+1)^2+(log n+1)(n^2+1)$ then: $$f(n) = n^2 \log^2n + 2n\log n + 1 + n^2\log n + n^2 + \log n + 1 \geq n^2log^2n$$ since all the other terms are obviously greater than 0. Therefore by definition $f(n) = \Omega (n^2log^2n)$. Which strictly means it cannot be bounded from above by anything ...


2

All is correct, but - it can be done in one step after you represent this expression as a sum of terms: $$\mathcal{O}(3m+2m⋅n⋅p+p⋅n+p⋅m)=\mathcal{O}(m⋅n⋅p)$$ because: The term $(m⋅n⋅p)$ dominates all the other terms - $(3m)$, $(p⋅n)$, and $(p⋅m)$ - in this sum. Constants are eliminated according to the $\mathcal{O}$ definition.


2

Time complexity of algorithms is usually given as big O. There are many reasons for this, including tradition, but when pertinent reason is that in some cases the time complexity depends on the input. For example, a sorting algorithm might run in $O(n\log n)$ in the worst case, but in $O(n)$ in the best case, and so it is not correct to say that it runs in $\...


Top 50 recent answers are included