algorithm - 分割統治アプローチを使用して配列要素を出力するアルゴリズムの実行時間

Question

サイズ n の配列 A があるとします。その中にいくつかの要素があります。目標は、それらをできるだけ早く印刷することです。印刷順は問いません。

素朴なアルゴリズムは、

print_number (A)
    for(i = 0 to n)
        print A[i]

そして、それは O(n) の時間の複雑さを持ちます

そして、下のものはどうですか？

print_number (A, l, r)
if (l == r)   // terminating condition
    print A[i]
else
    mid = (l+r)/2
    print_number (A, l, mid)
    print_number (A, mid, r)

これは O(n) になります

[編集済み]並列処理を使用する場合は、十分な数のプロセッサを想定してください。

print_number (A, l, r)
if (l == r)   // terminating condition
    print A[i]
else
    mid = (l+r)/2
    spawn print_number (A, l, mid) // assign to a new thread / processor
    print_number (A, mid, r)

O(lgn) でしょうか？またはO（n）？