Question

Give a big-O characterization, in terms of n, of the running time of the following method. Show your analysis!

public void Ex(int n)

int a = 1;

for (int i = 0 ; i < n*n ; i++)

for (int j = 0; j <= i; j++)

if( a <= j)

a = i;

}

EXPERT ANSWER

The Big-O upper bound on this algorithm is O(n^4).

Analysis:

To find the Big-O bound, we must multiply the nested loops. The outer