# Tag Info

Usually we call statement $A$ stronger than $B$ when $A$ implies $B$: $A \Rightarrow B$ (weaker-stronger). In other words, $B$ is weaker than $A$. When the presenter is speaking about linear time for partition, this is a stronger statement than $O(n)$ time. All linear functions are in $O(n)$, but it also contains non-linear functions. For example: $\sin n, \... 3 The partition needs really linear time Here, the presenter meant that partition takes$\Omega(n)$time. not just$O(n)$time Here, the presenter meant that this is a loose or weak statement. A stronger statement would be that partition takes$\Omega(n)$and$O(n)$time, which is equivalent to$\Theta(n)$, as you are saying. 2 For sufficiently large values of$n$, and$b>0$: $$( \log^*n )! < ( \log \log n )! < (\log \log n)^{\log \log n} = 2^{(\log\log n) \log \log \log n} \in o(2^{b \log n}) \subset o( (n \log n)^b ).$$ 1 Big-$O$is the set of functions $$O(f)=\{g\colon \exists C>0, \exists N \in \mathbb{N}, \forall n > N, g(n) \leqslant Cf(n) \}$$ So we can write$100n+5 \leqslant 105\cdot n$, taking$C=105, N=1$, and we obtain $$100n+5 \in O(n)$$ 1 Your guess works: if$T(n) \le c n^3$and$c \ge 2\$ then $$T(n) = 4c \frac{n^3}{8} + n^3 = \frac{c}{2} n^3 + n^3 = cn^3 \left(\frac{1}{2}+\frac{1}{c} \right) \le cn^3.$$