Textbook.

CS 3343/3341  Analysis of Algorithms  Fall 2012  Recitation 3  Big-Θ, Etc.     Partial Answers

---

1. The first problem will be made accessible during the Recitation hour: Rec 3, In-Class Problem 1 (password protected, use "CS3343" without quotes for "User Name" and password from class just before the recitation).

// Harmonic.java: harmonic function
public class Harmonic {
  


   static double harmonic0(int n) {
      double res = 0.0;
      while (n > 0) {
         res += 1.0/n;
         n = n - 1;
      }
      return res;
   }

   static double harmonic(int n) {
      if (n == 1) return 1;
      return 1.0/n + harmonic(n - 1);
   }

   public static void main(String[] args) {
      int n = 1000000000;
      double res;
      System.out.println("harmonic0:\n");
      res = harmonic0(n);
      System.out.println(res);
      System.out.println("harmonic:\n");
      res = harmonic0(n);
      System.out.println(res);
      System.out.println(res - Math.log(n));
   }
}

// harmonic.c: harmonic function
#include 
#include 
#define N 1000000000

double harmonic0(int n) {
   double res = 0.0;
   while (n > 0) {
      res += 1.0/n;
      n = n - 1;
   }
   return res;
}

double harmonic(int n) {
   if (n == 1) return 1;
   return 1.0/n + harmonic(n - 1);
}

void main() {
   double res;
   // printf("harmonic0:\n");
   // res = harmonic0(10);
   // printf("%20.16f\n", res);
   printf("harmonic:\n");
   res = harmonic0(N);
   printf("%20.16f\n", res);
   printf("%20.16f\n", res - log(N));
}

[with n = 1000000000 above, got, after 18 secs]
harmonic0:  21.30048150234615 [another 18 secs]

harmonic:   21.30048150234615
0.57721 56653 99737 8 [Correct to 10 places.
True value, Euler's Const:
0.57721 56649 01532 86060 65120]

[with N = 1000000000, got after 20 seconds]
 21.3004815023434091
0.57721 56653 96998 6
[recursive part ran for N = 100000,
gave segmentation fault with N = 1000000]

---

2. This problem is concerned with the weird problem: Newton's Method, Part 1: Square Root of Two. In printing results, you should print each successive approximation on a separate line, as we have done with the examples given in class.
   1. Alter the given simple Java or C code that calculates √2 so that it will calculate √10. Run the code to get output (as you are always supposed to do). (Change only the formula for x1. Leave the initial assignment x0 = 1 as it is.)

   2. Alter the given simple Java or C code that calculates √2 so that it will calculate √100000. Run the code. (Again change only the formula for x1. Leave the initial assignment x0 = 1 as it is.)

   3. Compare the answers to Part i and Part ii above and compare the number of loop iterations required. Could you have gotten the answer to Part ii from Part i with less computation?

// sqrt.c: find sqrt of input r
#include <stdio.h>
#include <math.h> // needed for fabs

double sqrt(double r) {
   double x0 = 1, x1;
   printf("%0.16f\n", x0);
   for ( ;  ;  ) {
      x1 = x0/2 + r/(2*x0);
      printf("%0.16f\n", x1);
      if (fabs(x1 - x0) < 1.0e-6) break;
      x0 = x1;
   }
   return x1;   
}

int main() {
   double r, x; 
   scanf("%lf", &r);
   x = sqrt(r);
   printf("\nsqrt(%0.16f) = %0.16f\n", r, x);
   printf("\nsqrt(r)^2 = %0.16f\n", x*x);
}

% cc -o sqrt sqrt.c -Wall
./sqrt
10
1.0000000000000000
5.5000000000000000
3.6590909090909092
3.1960050818746470
3.1624556228038903
3.1622776651756750
3.1622776601683795

sqrt(10) = 3.1622776601683795
sqrt(r)^2 = 10.0000000000000018
./sqrt
100000
1.0000000000000000
50000.5000000000000000
25001.2499900000984780
12502.6248950058488845
6255.3116077128715915
3135.6490107717154388
1583.7701676166232119
823.4553210954829865
472.4474090502862964
342.0555898147883909
317.2028655357482876
316.2292647723270420
316.2277660203895948
316.2277660168379612

sqrt(100000) = 316.2277660168379612
sqrt(r)^2 = 100000.0000000000145519

[The idea here is that sqrt(100000) = sqrt(10) * sqrt(10000) = sqrt(10) * 100. so we can easily get sqrt(100000) from sqrt(10). In using Newton's method for sqrt(100000), notice how initially each successive guess is half the size of the previous one, until we get close. Thus convergence from an initial guess of n takes log₂(n) steps until the rapid convergence at the end.]

---

3. Use Newton's method to find the unique solution to the equation cos(x) = x. (There is no closed formula for the answer, so the only option is an approximate solution.)
   1. Use x0 = 1 as your initial guess. [Hints: x is in radians, which is what C and Java use by default for cos. Look for a root of the equation f(x) = cos(x) - x. Remember that d/dx(cos(x)) = -sin(x). Print each successive approximation on a separate line. The answer starts out with 0.739....]

   2. What happens with x = -1 as the initial guess?

   3. What happens with x = -13 as the initial guess? [Be prepared for unusual output.]

// cosxeqx.c: find x such that cos(x) = x
#include <stdio.h>
#include <math.h> // needed for fabs
#include <stdlib.h> // needed for exit

double f(double x0) {
   double x1;
   printf("%20.16f\n", x0);
   int i;
   for (i = 0; i < 50000; i++ ) {
      x1 = x0 + (cos(x0) - x0)/(sin(x0) + 1);
      printf("%i: %0.16f\n", i, x1);
      if (fabs(x1 - x0) < 1.0e-6) break;
      x0 = x1;
   }
   return x1;   
}

int main(int argc, char *argv[]) {
   double r, x0;
   if (argc != 2) {
      printf("Usage: \"./cosxeqx 2\"\n");
      exit(1);
   }
   sscanf(argv[1], "%lf", &x0);
   r = f(x0);
   // printf("\nroot = %0.16f\n", r);
   // printf("check: cos(x) - x = %20.16f\n"
   //    cos(r) - r);
}

% cc -o cosxeqx -lm cosxeqx.c -Wall
./cosxeqx 1
  1.0000000000000000
0: 0.7503638678402439
1: 0.7391128909113617
2: 0.7390851333852839
3: 0.7390851332151607

root = 0.7390851332151607
check: cos(x) - x =  -0.0000000000000001
./cosxeqx -1
 -1.0000000000000000
0: 8.7162169587795688
1: 2.9760606550969126
2: -0.4257846886852312
3: 1.8511838177311819
4: 0.7660395196449302
5: 0.7392410674960820
6: 0.7390851385832758
7: 0.7390851332151607
./cosxeqx -13
-13.0000000000000000
0: 10.9852641445845709
1: -206870.8577400072827004
2: -22623.4680586579343071
3: -9750.7618152170707617
4: -3931.0644697052166521
5: -1750.9226439511676290
 . . . Complete output
885: -9.3630935494169414
886: -0.4485589518583601
887: 1.9345497592680314
888: 0.7506501329387815
889: 0.7391143090355287
890: 0.7390851334031108
891: 0.7390851332151607
./cosxeqx -11
(3618 lines)

[Note that in the above program, I used

x1 = x0 + (cos(x0) - x0)/(sin(x0) + 1);

for the iteration formula, but this can be simplified to

x1 = (x0*sin(x0) + cos(x0))/(sin(x0) + 1);]

In the image below, the green line is the "base line" y = -x.
The red line is the function at issue, y = cox(x) - x,
and the blue line is the derivative, y = -sin(x) - 1.

Click picture or here for full size picture.

---

4. Simplify the bound O(6*n*√n + 3*n² + 7*n^5/2) . [ See Big-Θ.] [This is the highest power of n, without the constant, or O(n^5/2.]

   ---

5. Problem 3.1-3 on page 56. [Explain why the statement, "The running time of algorithm A is at least O(n²)," is meaningless.] [To say "at least" means you are talking about a lower bound. But Big-O gives an upper bound.]

   ---

6. Problem 3.1-4 on page 56. [Is 2ⁿ⁺¹ = O(2ⁿ)? Is 2²ⁿ = O(2ⁿ)?] For credit you must give reasons for your answers. [2ⁿ⁺¹ is a constant times 2ⁿ, namely 2 * 2ⁿ, so the first answer is "Yes".
   On the other hand, 2²ⁿ = 2ⁿ * 2ⁿ, so it is not a constant times 2ⁿ, so the second answer is "No".]

   ---

7. Suppose it takes 5 seconds for a low-performance sort to sort 1000 items into order. Assume the sort has Θ(n²) performance. If the constant implied by the bound stays the same, how long would it take to sort 1000000 items?
   Now suppose a high-performance sort also takes 5 seconds to sort 1000 items into order. The better sort has performance Θ(n*log₂(n)). Again assuming the implied constant stays the same, how long would it take to sort 1000000 items into order.? [Answers: about 2 months and about 2.75 hours. (Note change in the second answer.)] (Note: I used log base 2 above just to make it more specific, but you get the same answer with log to any base.) [With the low performance sort, the ratio of times to do the big sort versus the small sort is 1000000² / 1000² = 10¹² / 10⁶ = 10⁶. Since the small sort takes 5 seconds, the larger will take 5 * 10⁶ sec = 1389 hours = 57.87 days.
   With the low performance sort, the ratio of times to do the big sort versus the small sort is (10⁶) * log₂(10⁶) = (10⁶) * 19.93157 compared to (10³) * log₂(10³) = 1000 * 9.96578. This ratio is exactly 2000. So the larger sort takes 2000 times as long, or 10000 sec = 2.7777 hours. With logs base 10, the 19.93 and the 9.96 above would be 6 and 3, so the ratio is still exactly 2000. In general, log(1000000) / log(1000) will be 2000 for any base.]