Section 22.3 Check Point Questions5 questions 

Count the number of iterations in the following loops.

(a)
int count = 1;
while (count < 30) {
  count = count * 2;
}

(b)
int count = 15;
while (count < 30) {
  count = count * 3;
}

(c)
int count = 1;
while (count < n) {
  count = count * 2;
}

(d)
int count = 15;
while (count < n) {
  count = count * 3;
}        

How many stars are displayed in the following code if n is 10? How many if n is 20? Use the Big O notation to estimate the time complexity.

(a)
for (int i = 0; i < n; i++) {
  System.out.print('*');
}

(b)
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    System.out.print('*');
  }
}

(c)
for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      System.out.print('*');
    }
  }
}

(d)
for (int k = 0; k < 10; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      System.out.print('*');
    }
  }
}

Use the Big O notation to estimate the time complexity of the following methods:

(a)
public static void mA(int n) {   
  for (int i = 0; i < n; i++) {
    System.out.print(Math.random());
  }
}

(b)
public static void mB(int n) {   
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++)
      System.out.print(Math.random());
  }
}

(c)
public static void mC(int[] m) {   
  for (int i = 0; i < m.length; i++) {
    System.out.print(m[i]);
  }

  for (int i = m.length - 1; i >= 0; )
  {
    System.out.print(m[i]);
    i--;
  } 
}

(d)
public static void mD(int[] m) {   
  for (int i = 0; i < m.length; i++) {
    for (int j = 0; j < i; j++)
      System.out.print(m[i] * m[j]);
  }
}

Design an O(n) time algorithm for computing the sum of numbers from n1 to n2 for (n1 < n2). Can you design an O(1) for performing the same task?

Example 7 in Section 22.3 assumes n = 2^k. Revise the algorithm for an arbitrary n and prove that the complexity is still O(logn).