All of these questions are from the algorithms fourth editio

All of these questions are from the algorithms fourth edition book by sedgewick I have checked the solution manual and the answers there are not what I am looking for please do not use them and also do not give me anything from github currently. Please use the algs jar file used for the book.

1.

1 + 1/N

(1 + 1/N)(1 + 2/N)

What’s unusual about these two tilde approximations

2. What’s the order of growth for

Int sum = 0;

   for(int n = N; n > 0; n /= 2)

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

           sum++;

Int sum = 0;

   for(int i = 1; i < N; i *= 2)

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

           Sum++;

3. I have this code here Under what conditions will lower_bound and upper_bound return the same index for some given array and key?               

//import edu.princeton.cs.algs4.*;

public class Bounds {

   public static int lower_bound(int[] a, int key) {

       // Your code here.

       int len = a.length;

       int low = 0;

       int high = len - 1;

       int mid = (low + high) / 2;

       int compare;

       Integer value;

       while (true) {

       value = a[mid];

       compare = value.compareTo(key);

       if (compare == 0 || compare > 0) {

       high = mid - 1;

       if (high < low) {

       return mid;

       }

       } else if (compare == -1) {

       low = mid + 1;

       if (high < low) {

       return mid < len - 1 ? mid + 1 : a.length;

       }

       }

       mid = (low + high) / 2;

       }

   }

   public static int upper_bound(int[] a, int key) {

       // Your code here.!

       int len = a.length;

       int lo = 0;

       int hi = len - 1;

       int mid = (lo + hi) / 2;

       int compare;

       Integer value;

       while (true) {

       value = a[mid];

       compare = value.compareTo(key);

       if (compare == 0 || compare < 0) {

       lo = mid + 1;

       if (hi < lo) {

       return mid < len - 1 ? mid + 1 : a.length;

       }

       } else {

       hi = mid - 1;

       if (hi < lo) {

       return mid;

       }

       }

       mid = (lo + hi) / 2;

       }

   }

   public static void main(String[] args) {

       // The int read from stdin is the size of the array.

       int n = StdIn.readInt();

       int[] a = new int[n];

       // The next n ints are the array itself.

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

           a[i] = StdIn.readInt();

       // Read keys until we have no more input. For each

       // key, call lower_bound() and upper_bound() and

       // show the results.

       while (!StdIn.isEmpty()) {

           int key = StdIn.readInt();

           int lb = lower_bound(a, key);

           int ub = upper_bound(a, key);

           StdOut.printf(\"%3d %3d\ \", lb, ub);

       }

   }

}

Solution

2:

For

for(int n = N; n > 0; n /= 2)

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

           sum++;

OR

For

for(int i = 1; i < N; i *= 2)

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

           Sum++;

Groth will be: O(log n)