Q1)

A. Prove or disprove (2 Pts.)

1. If f(n) is O(g(n)). Is then 2^f(n) = O(2 ^g(n))?

2. f(n) = O(g(n)), then g(n) = O(f(n)).

3. n^k = (2ⁿ)

4. log(n!) = (nlogn)

B) In each of the following situations, indicate whether f = O(g), or f = (g),

or both f = (g). (2 Pts.)

1. f(n) = 100n + log n and g(n) = n + (log n)².

2. f(n) = n^1.01 and g(n) = n log n.

3. f(n) = n^1/2 and g(n) = 4^{log n}

4. f(n) = 2ⁿ and g(n) = 2ⁿ⁺¹.

Q2.

A. Find the time recurrence equation and the complexity (2 pts.)

1.

int Fun1(int n)

{

if (n <= 0)

return 1;

for (int i=0;i

constOperation;

return 1 + Fun1(n-1);

}

2.

int Fun2(int n)

{

if (n <= 0)

return 1;

for (int i=0;i

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

constOperation;

return 1 * Fun3(n/2);

}

B) Write D&C algorithm to search about an item K in a list. (2 Pts.)

Q3)

1. what is the P, NP, NP-hard and NP-complete? (1 Pts.)

2. What are the steps of converting the hard problem into NP-Complete? (1 pts.)