What would be a growth function for the following code fragm

What would be a growth function for the following code fragment? the size of the problem is expressed as n.

public static int foobar(int n) {

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

foo(2);// how many times does foo run?

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

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

foo(11); //including this.

}

Solution

Assuming the function called \' foo() \' in the given function \'foobar(int n) is not a reccursive function, lets say the function calls foo(2) and foo(11) takes a constant amount of time, \'K\'.

Now, We will define the function for the running time of the function foobar(int n).

Lets say T(n) denotes the running time for the function, foobar(int n).

In the function, the first for loop is iterated for \'5\' number of times and in each iteration we are doing one single operation i.e., execution of the functin foo(2). Thereby the total time taken by the first \'for loop\' will be \' 5*K \'.(We have assumed k as the constant time taken by the function foo())

The second for loop is a one level nested for loop in which the function call foo(11) is called for n*n number of times.

So total number of operations that are done in the function call foobar(n) will be 5*k+n*n*k.

Hence, T(n) = 5k + k*n²

T(n) = kn² + c ( c is a constant)

As per the definition of the Asymptotic notations, We can say that the T(n) = O( n²).

or

The growth function for the function foobar() will be n²