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
