0

For this question part A,I know the Big-O is n^2, because the outer loop can run at most (n-1) times, and each inner loop can run at most (n(n+1))/2 = n^2/2 + n/2 , and since we are calculating the Big-O, we only take the higher bound, hence, we have (n * n) = O(n^2).

But for part B, I know the array is A[1.....n] = {1,1,4,7,10,..,3(n-2)+1}, and

From my understand, the outer loop have at least (n-1) iterations, and the inner loop have at least (n/2) iterations. So we have (n*n/2) = (cn^2) = (n^2), is this correct?

According to the answer sheet, there are at least n^2/4 iteration, which is Big-Omega(n^2), I just don't understand how they get to n^2/4 and not n^2/2, can someone explain how to do part B in detail please, Thanks.

enter image description here

Ohhh
  • 415
  • 2
  • 5
  • 24
  • possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – David Eisenstat Aug 28 '14 at 23:34
  • I know all that (Big-O, Big-Omega, and stuff), but I am asking for to find Big-Omega for this particular problem. – Ohhh Aug 28 '14 at 23:41
  • 1
    The inner loop has n/2 iterations on average, but only n/2 instances have at least n/2 iterations. The constant ultimately doesn't matter. – David Eisenstat Aug 29 '14 at 00:16

1 Answers1

2

You are correct the best case time complexity of the bizzare() procedure is Big-Omega (n^2/2) assuming that the inner-loop gets executed for all i.

Look at it this way:

Let n = A.size(), 
so for the first time when i=2 the inner loop will run atleast once,
when i=2, the inner loop will run atleast twice
when i=3, inner loop runs atleast thrice and so on

So the total best case complexity is actually Big-Omega(sum of first n-1 natural numbers) = Big-Omega(n*(n-1)/2) = Big-Omega(n^2). Also, note that Big-Omega(n^2/2)=Big-Omega(n^2/4). If you take average of outer loop * average of inner loop that will give you n^2/4 iterations on average assuming that the distribution of data is uniform which means half will go to the if block and half will go to the else block. The constant really doesnt matter.

Shankhoneer Chakrovarty
  • 690
  • 1
  • 6
  • 19