For the following code snippet, provide line-by-line analysis and construct function T(n) that give the run time of this code snippet as a function of “n”. Also determine the big-O of for this code snippet.
x = 10,000;
for (int i = 1; i <= n; i++) {
if ( x < i)
sum += foo( i );``
system.out.print(sum);
else
for (j = 1; j <= i; j++)
system.out.print( i );
system.out.println( );
}
foo (a) {
for (int i = 0; i < n; i++)
sum += a * i;
return sum;
}
x = 10,000;
1: takes 1 fixed arbitrary length of time total making this O(1)
for (int i = 1; i <= n; i++) {
2: run n times so time is now O(n) since O(n) >> O (1) [where >> means much greater than]
if ( x < i)
sum += foo( i );``
system.out.print(sum);
3: these lines run in O(n) thanks to the for loop in foo, so since this is nested, time here is O(n^2) for n > 10000
else
for (j = 1; j <= i; j++)
system.out.print( i );
system.out.println( );
}
4: This will run n times within the loop as well, so O(n^2) for time <10000
foo (a) {
for (int i = 0; i < n; i++)
sum += a * i;
return sum;
}
5: see 3rd comment
Final: Since this runs in O(n^2) for n >10000 and n < 10000 this function is O(n^2)