Analysis of Typical Loops
for( int j = 1; j < n; j++ )
for( int k = j; k > 0; k = k/2 )
{
O(1)
}
log(1) + log(2) + É + log(n-2) + log(n-1)
ë
O(n log(n)).
n/2 terms, each
>
log(n/2) => bound is tight
