72 a Let f be a function whose domain is R Show that if f O

7.2

(a)

Let f be a function whose domain is R⁺. Show that if f = O(n), then f = O(n²)

(b)

Let f be a function whose domain is R⁺. Show that if f = O(n), then it is not true that f = (n²).

7.3

(a)

Characterize the input that will cause the \"If\" statement in the inner loop to execute the most number of times.

(b)

Give an asymptotic lower bound for the running time of the algorithm based on your answer to the previous question.

(c)

Was it important to use the worst-case input for the lower bound? That is, would any input of a given length have resulted in the same asymptotic lower bound?

(d)

Give an upper bound (using O-notation) for the time complexity of the algorithm that matches your asymptotic lower bound for the algorithm.

9.3

Suppose that the prime factorizations of two positive integers x and y are expressed using a common set of primes as follows:

·       x = p₁₁·p₂₂p_nn

·       y = p₁₁·p₂₂p_nn

(a)

What is the prime factorization for x · y?

p₁^{min{1, 1}}·p₂ ^{min{2, 2}} · ·p_n ^{min{n, n}}

(b)

Suppose y | x. What is the prime factorization for x / y? (It is fine to have some prime factors raised to the zero power in your answer.)

Solution

a) If f(n) is O(g(n)) then here g(n)=n
   there exist a constant c > 0, and a constant n₀ such that for all n n₀: f(n) c*g(n) ==c*n

hence:
   there exist a constant c > 0, and a constant n₀ such that for all n n₀: g(n) (1/c)*f(n) ==n>=i/c*f(n)
     note that since c > 0, then the constant (1/c) > 0

hence:
   there exist a constant k > 0, namely k = (1/c), and a constant n₀ such that for all n n₀: g(n) k*f(n) =>g(n) >=n/c*n

==g(n)<=1/c*n²

which is the definition of g(n) =O(n²)).

b)

If f(n) is O(g(n)), here g(n)=n
   there exist a constant c > 0, and a constant n₀ such that for all n n₀: f(n) c*g(n)

hence:
   there exist a constant c > 0, and a constant n₀ such that for all n n₀: g(n) (1/c)*f(n)
     note that since c > 0, then the constant (1/c) > 0

hence:
   there exist a constant k > 0, namely k = (1/c), and a constant n₀ such that for all n n₀: g(n) k*f(n)

which is the definition of g(n) = (f(n)). = (n) but not (n²)

7.3) a ) The input which causes the inner loop to execute most number of times is

For example :

7.3)b)an asymptotic lower bound for the running time of the algorithm above : O(nⁿ) ,taking log , we get O(nlogn) for lower bound