Time complexity of a function with while loops and an if statement

Question

int dup_chk(int a[], int length) 
{
  int i = length;
  while (i > 0)
  {
    i--;
    int j = i -1;
    while (j >= 0)
    {
      if (a[i] == a[j])
      {
        return 1;
      }
      j--;
    }
  }
  return 0;
}

So what I think I know is the following:

• line 1 is just 1.
• First while loop is N+1.
• i--; is N times since its inside the first while loop.
• j = i -1; is also N.
• Second while loop is (N+1)N = N^2+N since its a while loop within a while loop
• if statement: ???
• j--; is N(N) = N^2
• return 0; is 1

I'm really new to calculating the time complexity of algorithms so I'm not even sure if what I think I know is completely right. But what is messing with me is the if statement, I do not know how to calculate that (and what if there is an else after it as well?)

EDIT: The grand total is equal to 3/2N^2 + 5/2N+3 I understand that this function is O(N^2) but don't quite get how the grand total was calculated.

Answer 1

Usually such accurate analysis of time complexity is not required. It suffices to know it in terms of Big-O. However, I did some calculations for my own curiosity.

If your concern is just a worst case analysis to obtain the time complexity, consider an array with only unique elements. In such a scenario:

• The return 1 statement never executes. The inner while loop executes N(N-1)/2 times (summation i-1 from 1 to N), and three things happen - the while condition is checked (and evaluates to true), the if condition is checked (and evaluates to false) and the variable j is decremented. Therefore, the number of operations is 3N(N-1)/2.
• The outer while loop executes N times, and there are three statements apart from the condition check - i is decremented, j is assigned, and the inner while condition fails N times. That is 4N more operations.
• Outside all loops, there are three more statements. Initialisation of i, the while condition fails once, and then the return statement. Add 3 more to our tally.

3/2N² - 3/2N + 4N + 3.

That's 3/2N² + 5/2N + 3. There is your 'grand total'.

To repeat myself, this calculation is completely unnecessary for all practical purposes.