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
Related Tags
asymptotics × 1173landau-notation × 214
algorithms × 181
algorithm-analysis × 177
time-complexity × 176
recurrence-relation × 162
runtime-analysis × 127
complexity-theory × 97
big-o-notation × 74
master-theorem × 53
terminology × 43
recursion × 30
proof-techniques × 25
notation × 23
data-structures × 22
graphs × 19
mathematical-analysis × 19
sorting × 15
lower-bounds × 12
loops × 12
upper-bound × 12
combinatorics × 9
discrete-mathematics × 9
optimization × 8
heaps × 8