New answers tagged

0

Holds $$\Theta=O \cap \Omega$$


0

Suppose that $n \geq 1$ and $d \geq 2$. On the one hand, $$ \lceil \log_d(n(d-1)+1)-1 \rceil \leq \log_d(2dn) \leq \log_d n + 2. $$ On the other hand, $$ \lceil \log_d(n(d-1)+1)-1 \rceil \geq \log_d(nd/2)-1 = \log_d n - 1. $$ In other words, your expression is equal to $\log_d n$ up to a constant additive term. In particular, if we fix $d$ then your ...


1

A function $g(n)$ is an asymptotic lower bound for a function $f(n)$, in symbols $f(n) = \Omega(g(n))$, if the following holds: There exist $N,c > 0$ such that for all $n \geq N$: $f(n) \geq cg(n)$. In your case, $f(n) = 3n^2 + 2n$. You can check that $f(n) = \Omega(f(n))$, that is, the function is its own asymptotic lower bound. Similarly, you can ...


0

Suppose $f\in \Theta(g)$ and $h\notin \mathcal{O}(g)$. That means: $$\exists A>0, B>0, \forall n\geqslant 0, Ag(n) \leqslant f(n) \leqslant Bg(n)$$ and $$\forall C>0, \exists n\geqslant 0, h(n) > Cg(n)$$ Therefore, for all $C>0$, there exists $n\geqslant 0$ such that $h(n) > (C-A)g(n)$. We conclude that $f(n) + h(n) > Ag(n) + (C-A)g(n) = ...


-1

Firstly, Input size(n)- Total length[size] Input(v)- Value(s) Given a linear data-structure A = [34,52,42,4,422] where n = 5 and v = [34,52,42,4,422] Now coming to the Θ notation which provides an asymptotically tight bound i.e. For all n [input size] >= n0, function f(n) belongs to (equal to) g(n), within some constant factors. The worst case of ...


Top 50 recent answers are included