How to find asymtotic run time of this method?

Question

I was asked to write this method and then give the asymptotic run time in terms of the size of the array. Could someone explain to me how this is done?

public int doSomething(int[] nums) {
    int count = 0;

    for (int i = 0; i < nums.length; i++)
        for (int j = 0; j < i; j++)
            if (nums[i] > nums[j])
                count++;

    return count;
}

Answer 1

The problem size N is the length of nums.

The way to decide asymptotic runtime from code where there are only for-statements is pretty straightforward.

Asymptotic runtimes are described by traditional notation like

O(N)

Which is one simple for-statement. We need to process the input elements only once.

Nested for-statements like you have means we need to check the value of each nums more than once.

You are repeating N times in the outer loop. You are repeating a number of times dependent on N in the inner loop.

Also how do you print a triangle like

*
**
***
****
*****
******

The number of elements in the triangle is proportional to N²

Answer 2

Well run time is usually how many steps you have to do.

Asymptotic run time is almost the same, but you can do some "magic" to simplify your result.

In your case you have cycle for (int i = 0; i < nums.length; i++) which does nums.length steps. And in every step, you do for (int j = 0; j < i; j++).

Well at first, you do only 1, then you do 2 steps, than 3 steps etc.

Run time is 1 + 2 + 3 + 4 + 5 + 6 + .... + n, using summation of series you get : n*(n+1)/2

Asymptotic run time is based on some rules. In our case, you can get rid off constants, only n is important, therefore n*(n+1)/2 = Theta(n*(n)) = Theta(n^2)

Result : n^2