0

I believe that the runtime of func2 is O(n * log(n)).
But some people have told me that it's not.

int func2(int* arr, int n){
    int i, j;

    for (i = 1; i <= n; i *= 2)
        reverseArray(arr, i);
    }
}

void reverseArray(int* arr, int n){
    int left, right, temp;

    for (left = 0, right = n-1; left <= right; left++, right--){
        temp = arr[left];
        arr[left] = arr[right];
        arr[left] = temp;
    }
}
David G
  • 94,763
  • 41
  • 167
  • 253
Damian Siniakowicz
  • 127
  • 4
  • 3
    `reverseArray()` runs in O(n) time and is executed O(log n) times therefore the time complexity is O(n log n). – David G Oct 23 '18 at 02:48
  • Is `for(i=1;i<=n;i*=2)` O(log(n)) or O(0.5n) therefore O(n)? – Red Cricket Oct 23 '18 at 02:55
  • If `n == 64`, then i goes `1, 2, 4, 8, 16, 32, 64`. Is 7 closer to log(n) or 0.5n? – Jim Mischel Oct 23 '18 at 03:12
  • 1
    @0x499602D2 The time complexitiy of `reverseArray()` is indeed O(n), but it depends on the variable `i`, not `n`. As @santanu kar shows, the total run-time complexity is a sum of a geometric series with log(n) terms that grows exponentially, hence linear. – dobkind Oct 23 '18 at 15:46
  • @dobkind Ah that's right – David G Oct 25 '18 at 02:32

1 Answers1

4

func2 runs in linear time, i.e., O(n)

Explanation:

It's easy to say time complexity of reverseArray method is linear, i.e., big-Theta(n)

let's assume func2 is called with n = 8;

The calls to reverseArray will be:-

reverseArray(arr, 1)
reverseArray(arr, 2)
reverseArray(arr, 4)
reverseArray(arr, 8)

So total runtime = 1 + 2 + 4 + 8 = 15, i.e. 2*8 - 1

So, if n was a power of 2, total run time = O(2*n - 1)

If n was not a power of 2, total run time would be = O(2*K - 1), where K is the highest power of 2 less than n. We can safely say, O(2*K - 1) = O(2*n - 1) [since, O is upperbound]

O(2*n - 1) = O(n)

For theta notation, lower bound is O(2*K - 1), where K is the highest power of 2 less than n. Therefore, time complexity = Theta(2^(floor(log(n)base2)+1))

Shree
  • 10,835
  • 1
  • 14
  • 36
santanu kar
  • 93
  • 4