Question

Big-O: Describe the worst case running time of the following pseudocode or functions in Big-Oh notation in terms of the variable n. Show your work

a) O( )

int m1(int n, int m) {

if (n < 10) return n;

else if (n < 100)

return happy (n - 2, m);

else

return happy (n/2, m);

}

-----------------------------

b) O ( )

void m2 (int n) {

j = 0;

while (j < n) {

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

{ System.out.println(”i = ” + i);

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

System.out.println(”k = ” + k);

}

j = j + 1; }

}

---------------------------

c) O ( )

void m3 (int n) {

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

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

System.out.println(”k = ” + k);

for (int j = n; j > 0; j--)

System.out.println(”j = ” + j);

}

} ------------------

d) O ( )

void m4 (int n, int x) {

for (int k = 0; k < 500; ++k)

if (x > 500) {

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

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

System.out.println(”x = ” + x);

}

}

Answer 1

Time Complexity of Each function in Big-oh notation.

In order to provide clear explaination of time compexity of each statement in function,i have added comment after each statement of funtion which represent time complexity of that statement.

(a) O( )

int m1(int n, int m) {

if (n < 10) return n;  //------>0(1)=constant

else if (n < 100) //------>0(1)

return happy (n - 2, m); //------>0(1)+Time Complexity of "happy(n - 2 , m)"

else

return happy (n/2, m); //------>0(1)+Time Complexity of "happy(n - 2 , m)"

}

Total time complexity = 0(1) + 0(1) + 0(1)+Time Complexity of "happy(n - 2 , m) + 0(1)+Time Complexity of "happy(n - 2 , m)

m1() = 0(1)+Time Complexity of "happy(n - 2 , m) (ANSWER)

Note:- We can not determine time complexity of function m1 in terms of variable n unless we know time complexity of funtion happy().

(b) O( n³ )  

void m2 (int n) {

j = 0; //------>0(1)

while (j < n) { //------>0(n)

for (int i = 0; i < n; ++i) //------>0(n²)

{ System.out.println(”i = ” + i);   //------>0(1)

for (int k = 0; k < i; ++k) //------>(1+2+3+......+n)*n = (n(n+1)/2)*n = 0(n³)

System.out.println(”k = ” + k); //------>0(1)

}

j = j + 1; } //------>0(1)

}

There are 2 "for" loop.For every iteration of "outer for" loop "inner for" loop is execute.

Total time complexity of function m2() = 0(1)+0(n)+0(n³)+0(1)

m2() = O ( n³ ) (ANSWER)

(c) O( n⁴ )  

void m3 (int n) {

for (int i = 0; i < n * n; ++i) { //------>0(n²)

for (int k = 0; k < i; ++k) //------>(1+2+3+......+n²) = n²(n²+1)/2 = 0(n⁴)//For every outer for loop this loop is executed.

System.out.println(”k = ” + k); //------>0(1)

for (int j = n; j > 0; j--)) //------>0(n)

System.out.println(”j = ” + j); //------>0(1)

}

} ------------------

Total time complexity of function m3() = 0(n²)+0(n⁴)+0(1)+0(n)+0(1)

m3() = O ( n⁴) (ANSWER)

(d) O ( n² )

void m4 (int n, int x) {

for (int k = 0; k < 500; ++k) //------>0(1)

if (x > 500) {

for (int i = 0; i < n * k; ++i) //------>0( n )

for (int j = 0; j < n; ++j) //------>0( n² )

System.out.println(”x = ” + x); //------>0(1)

}

}

Total time complexity of function m4() = 0(1)+0(n)+0(n²)+0(1)

m4() = O (n²) (ANSWER)