Homework 2

Due: Tuesday, 2/20/2022, by 8:00am

Overview

Do your own work for this assignment; do not work with others. Consult the resources provided and your professor for help if you need it. Please type your answers. Use good grammar, correct spelling, and complete sentences. This assignment will be submitted on iLearn by the deadline and you will bring a physical printed copy at the beginning of class whenever that is for your section. Homework turned in after the deadline will not be accepted. Homework turned in after I have collected it will lose 20%. Please do not email late homework to your professor.

Total points: 90.

Assignment

1. (10 points each, 30 points total) Analyze these functions. For each function, give the complete T(n) (or T(m,n), or whatever is appropriate), then find the tightest time complexity you can, in big-Oh notation. You need not show every step in getting from T(n) to big-Oh. You should assume all inputs are > 0.
a)

int f1(int n) {                   // COST   TIMES
  int i = 1;                      // c1     1
  for (int j = 1;                 // c2
                j <= n;           // c3
                        j++) {    // c4
    i = i * j;                    // c5
  }
  return i;                       // c6
}

int f2(int m, unsigned int n) {        // COST   TIMES
  for (int i = 0;                      // c1     1
                i < 2 * m;             // c2
                           i++) {      // c3
    for (int j = n;                    // c4
                    j > 0;             // c5
                           j--) {      // c6
      return j;                        // c7
    }
  }
  return 0;                            // c8
}

void f3(int n) {                          // COST   TIMES
  for (int i = 0;                         // c1     1
                i < n;                    // c2
                       i++) {             // c3
    for (int j = 10;                      // c4
                   j >= 0;                // c5
                           j--) {         // c6
      System.out.print("i = " + i);       // c7
      System.out.println(", j = " + j);   // c8
    }
  }
}

2. (10 points) Will the following Java function always terminate, for any input? Prove your answer. You should assume for this problem that the int type does NOT wrap around (it can count to any integer, positive or negative).
```
int g(int n) {
  int x = g(n - 1);
  if (x > 0) {
    return x + 1;
  } else {
    return 1;
  }
}
```

3. (10 points) Consider a standard binary tree with n nodes, where every node has a pointer to two children, either of which may be null. In this tree, are there more null child pointers, or non-null child pointers? Prove your answer. Remember that n could be any integer greater than zero, so we're not just talking about one particular tree for some fixed n, but ANY tree.

4. (10 points) Exercise 2.11 in your textbook. For this problem and the next one, consider setting up an equation T(n1)/t1 = T(n2)/t2. Think about what this equation means.

5. (10 points) Exercise 2.12 in your textbook. For part (b), you will need to use some guess-and-check to find the answer.

6. (10 points) Exercise 3.27 in your textbook (here "stack space" means the "space on the runtime stack" — the stack that stores function calls and local variables).

7. (10 points) Exercise 3.36 in your textbook. Think outside the box on this one. The answer is simple.

Unrelated...

Check this out. It is a good cause; together we can support our wounded warriors.