下列程序段的时间复杂度是 ( ) .
int sum $=\theta$;
for (int $i=1 ; i<n ; i^{*}=2$ )
for (int $j=0 ; j<i ; j++)$
sum++;
A. $O(\log n)$
B. $O(\mathrm{n})$
C. $O(\mathrm{n} \log \mathrm{n})$
D. $O\left(\mathrm{n}^{2}\right)$
令 $n=2^{m}, n$ 是 2 的整数倍, $m=\log _{2} n_{\circ}$ sum ++ 的语句频度 $1+2+4+\cdots \cdots+2^{m}=1+\frac{2\left(1-2^{m}\right)}{1-2}=$ $1+2 \times 2^{m}-2=2 \times 2^{m}-1=2 n-1$ 。因此, 时间复杂度为 $O(n)$ 。

因此答案为：B