Analysis of Typical Loops
for( int j = n; j > 0; j = j/2 )
for( int k = 1; k <= j; k++ )
{
O(1)
}
n + n/2 + n/4 + É + 1 < 2n
Therefore
ë
O(n).