CODEWITHSUNDEEP
time-complexitybig-opseudocode
Nick
Nick

Reputation: 47

Time complexity of below pseudocode

void buzz(int num, int [] a)
{
    for(int i=1;i<num;i*=2){
      for(int j=0;j<a[i]%num;j++){
          print(num);
      }
    }
}

I understand that the outer for loop runs for log n times. Need help in understanding the complexity of the inner loop and the overall.

Upvotes: 0

Views: 42

Answers (1)

user1196549
user1196549

Reputation:

Let us assume num = 2^n for simplicity.

The inner loop runs a[i] % num times, which is comprised in range [0, num-1]. The outer loop runs n times so you can conclude O(num.log(num)) = O(n.2^n) worst-case complexity.

For a precise evaluation, let r[i] := a[i] % num. Then the number of print's is

r[1] + r[2] + r[4] + r[8] + ... r[2^(n-1)].

This is n times the average r (for the relevant indexes; the expectation of r could be (num-1)/2)).

Upvotes: 1

Related Questions