Question

Give a big-Oh characterization, in terms of n,of the running time for each of the following code segments (use the drop-down): - public void func1(int n) { A. @(1). for (int i = n; i > 0; i--) { System.out.println(i); B. follogn). for (int j = 0; j <i; j++) System.out.println(j); c.e(n). System.out.println("Goodbye!"); D.@(nlogn). E.e(n). F.ein). public void func2 (int n) { for (int m=1; m <= n; m++) { system.out.println (m); i = n; while (i >0){ system.out.println(i); i = i / 2; public void func2(int size) { if (size%2 == 0) System.out.println("Even elements"); else System.out.println("Odd elements");

Answer 1

public void func1(int n) { for (int i = n; i > 0; i--) { System.out.println(i); for (int j = 0; j <i; j++) System.out.println(j); System.out.println("Goodbye!");

outer for loop is running for i = n to i = 1 (>0) which means total n times. inner for loop is running for j = 0 to j = i-1 (<i) which means i times so,

• when i = n in outer loop, inner loop will run n times
• when i = n-1 in outer loop, inner loop will run n-1 times
• .....................
• when i = 1 in outer loop, inner loop will run 1 time

Total = n + n-1 + n-2 + ..... + 2 + 1 = n(n+1)/2 = $\small \frac{n^2}{2} + \frac{n}{2}$ =  $\bold{\theta(n^2)}$

public void func2 (int n) { for (int m=1; m <= n; m++) { system.out.println (m); i = n; while (i >0){ system.out.println(i); i = i / 2;

for loop is running for m = 1 to m = n which means total n times. while loop inside for loop is running for fixed logn times (every time value of i is divided by 2) .

Total = n*(logn) = nlogn =  $\bold{\theta(nlogn)}$

public void func2(int size) { if (size%2 == 0) System.out.println("Even elements"); else System.out.println("Odd elements");

There are no loops. If-else condition will take constant time as there is only one print statement which will get executed.

Total = C (constant) =  $\bold{\theta(1)}$

public void func1(int n, String msg) { int i=0, j=0, k=0; for (i = n; i > 0; i--) for(j = 0; j<i; j++) for (k = 0; k < 1000; k++) System.out.println(msg);

outer-most for loop is running for i = n to i = 1 (>0) which means total n times. outer for loop is running for j = 0 to j = i-1 (<i) which means i times. Inner for loop will run 1000 time for each value of j which is constant. so,

• when i = n in outer-most loop, outer loop will run n times => Inner loop will run 1000*n times
• when i = n-1 in outer-most loop, outer loop will run n-1 times => Inner loop will run 1000*n-1 times
• .....................
• when i = 1 in outer-most loop, outer loop will run 1 time => Inner loop will run 1000 times

Total = n*1000 + (n-1)*1000 + (n-2)*1000 + ..... + 2*1000 + 1*1000 = 1000*(n(n+1)/2) = $\small \frac{500n^2}{2} + \frac{500n}{2}$ =  $\bold{\theta(n^2)}$

Note that higher order polynomial is considered as complexity.