CODEWITHSUNDEEP
javaalgorithmbig-ofunction-calls
user5987642
user5987642

Reputation:

How to calculate Big O for this algorithm?

I want to find the Big O of method1.

public static void method1(int[] array, int n)
{
    for (int index = 0; index < n - 1; index++)
    {
        int mark = privateMethod1(array, index, n - 1);
        int temp = array[index];
        array[index] = array[mark];
        array[mark] = temp;
    } // end for
} // end method1

public static int privateMethod1(int[] array, int first, int last)
{
    int min = array[first];
    int indexOfMin = first;
    for (int index = first + 1; index <= last; index++)
    {
        if (array[index] < min)
        {
            min = array[index];
            indexOfMin = index;
        } // end if
    } // end for
    return indexOfMin;
} // end privateMethod1

My thinking is that we need not care about privateMethod1, is this true? Do we need not worry about function calls while calculating Big O and just consider other factors like assignment operations in our method1?

Thanks.

Upvotes: 2

Views: 1183

Answers (2)

dfrib
dfrib

Reputation: 73206

Only operations that run in constant time, O(1), can be considered basic operations in your analysis of the running time of your algorithm; in this specific case, finding an upper asymptotic bound for you algorithm (Big-O notation). The number of iterations in the for loop of your method privateMethod1 depends on index in method1 (which itself depends on n) as well as on n, and does clearly not run in constant time.

Hence, we need to include privateMethod1 in our Big-O analysis of your algorithm. We'll treat all other operations, such as assignments and if statements as basic operations.

Treated as basic operations in our analysis:

/* in 'method1' */
int temp = array[index];
array[index] = array[mark];
array[mark] = temp;

/* in 'privateMethod1' */
int min = array[first];
int indexOfMin = first;

//...

if (array[index] < min)
{
    min = array[index];
    indexOfMin = index;
}

With this cleared up, you can analyse the algorithm using Sigma notation: the outer sum describes the for loop in method1, and the inner loop describes the for loop in privateMethod1, and the 1 generalizes "the cost" of all basic operations in the inner for loop.

enter image description here

Hence, an upper asymptotic bound for your algorithm method1 is O(n^2).

Upvotes: 1

taskinoor
taskinoor

Reputation: 46037

My thinking is that we need not care about privateMethod1,is this true?

No, you are wrong. You need to care about other function calls while calculating complexity. privateMethod1 runs in O(n) time since at worst case fist will be 0 and last is always n - 1. So your overall loop, i.e. method1 runs in O(n ^ 2) time.

Upvotes: 1

Related Questions