ببینید حلقه‌ی داخلی n بار اجرا میشه بعد n نصف میشه دفعا بعد حلقه داخلی ۲/n بار اجرا میشه و به همین ترتیب میشه نوشت

$n \frac{n}{2} \frac{n}{4} \frac{n}{8} ...=n(1 \frac{1}{2} \frac{1}{4} \frac{1}{8} ...)=n\sum_{i=0}^{lgn}(\frac{1}{2^{i}})=2n=\bigcirc (n)$