8

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. $$


Only top voted, non community-wiki answers of a minimum length are eligible