Search code examples
algorithmtime-complexitybig-oanalysis

calculate big oh notation with for loop condition

I am trying to understand the calculation of Big-oh notation of a function, when a function contains a for-loop, which has a specific condition

for (initialization, condition, increment)

or() like below:

    public void functE( int n ) 
    {
       int a;
       for ( int i = 0; i < n; i++ )
           for ( int j = 0; j <= n - i; j++ )
               a = i;
    }

I suppose the big-oh of this function to be O(n^2), is this valid?

Solution

  • Assuming a = i takes 1 time unit, you can consider each i:

    • i = 0 : n + 1
    • i = 1 : n
    • i = 2 : n - 1
    • ...
    • i = n - 1 : 2

    So in total:

    T(n) = (n+1) + (n) + (n-1) + ... + 2 = n + [1 + ... + n] = n + n * (n + 1)/2 = (n^2 + 3n) / 2 = O(n^2)