for-loop - 複雑さ - サイクルの bigtheta 3

Question

問題を解決しただけですが、その解決策を持っていないので、私の解決策が正しいかどうかを確認できるかどうかお願いします

int h=1; int cont = 0;

for (j = 2^N; j>1; j = j/2) {
        h = h * 2;
        for (i =1; i < j; i = i*2)
           for (k=2; k<h; k++)
               cont ++;
}

BIGTHETA でコードのその部分の複雑さを見つけなければなりません。

だから、私は3番目のサイクルがそのように成長することを分析します

k -> linear until = h (h は 2^w のように大きくなる) - したがって、複雑さは log n です。

2番目については、最初のサイクルの制限は0なので、複雑さはlog nだと思います。

最初の 2^N = 2^N-1 について、複雑さは n

合計の複雑さは n * log n です

Answer 1

シグマ表記法を使用して、段階的に正式に進めることができます (いくつかの手順をスキップしましたが、必要に応じて詳細を尋ねてください)。