Question

1.Let f and g be two functions such that f(n)/g(n) converges to a positive value less than 1 as n tends to infinity. Which of the following is necessarily true?

Select one:

a. g(n)=Ω(f(n))

b. f(n)=Ω(g(n))

c. f(n)=O(g(n))

d. g(n)=O(f(n))

e. All of the answers

2.

If T(n)=n+2^{3 log(2n)} where the base of the log is 2, then which of the following is true:

Select one:

a. T(n)=θ(n^2)

b. T(n)=θ(n)

c. T(n)=θ(n^3)

d. T(n)=θ(3^n)

3.

Let f and g be positive functions. Which of the following statements is true?

Select one:

a. If f(n) is Ω(g(n)) then there is only a finite set of values for which f(n) < g(n).

b. If f(n) is Ω(g(n)) then lim_n→∞ f(n)/g(n) >= 1.

c. f(n) is Ω(g(n)) iff for all n >= n₀, g(n)/f(n) <= c, where n₀ and c are positive constants.

d. If f(n) is Ω(g(n)) then lim_n→∞ g(n)/f(n) exists and is not infinity.

4.

Let f(n)=2nf(n)=2n and let g(n)=3ng(n)=3n. Which of the following is true?

Select one:

a. f(n)f(n) is O(g(n))O(g(n))

b. f(n)f(n) is Θ(g(n))Θ(g(n))

c. Neither function is an asymptotic upper bound of the other

5.

Let f and g be two functions such that f(n)/g(n) converges to 0 as n tends to infinity. Which of the following is necessarily true?

Select one:

a. f(n)=O(g(n))

b. f(n)=Ω(g(n))

c. f(n)=θ(g(n))

6.

Suppose that an algorithm runs in time T(n)=n^2+10n where n is the size of the input. Which of the following is not true:

Select one:

a. T(n) is O(n^2)

b. T(n) is O(n^3)

c. T(n) is Ω(n)

d. T(n) is Ω(log n)

e. T(n) is O(n)

7.

Suppose that an algorithm runs in time T(n)=(log n)^4+n log n where n is the size of the input. Which of the following is not true:

Select one:

a. T(n) is O(n^2)

b. T(n) is O(n log n)

c. T(n) is θ(n log n)

d. T(n) is Ω(n^4)

e. T(n) is Ω(n log n)

8.

Suppose the running time of an algorithm whose input has size nn is T(n)=n2+nlognT(n)=n2+nlog⁡n. Which of the following statements is always true.

Select one:

a. The algorithm runs in polynomial time.

b. The algorithm doesn't run in polynomial time.

c. Whether or not the algorithm runs in polynomial time depends on the value of n.

9. Suppose T(n)=3n2+2n+1T(n)=3n2+2n+1. What is the smallest value of cc such that T(n)≤cn2T(n)≤cn2 for all n≥1n≥1?

10. ∑j=1 ∑ji=1i=Θ(nc)∑j=1n∑i=1ji=Θ(n^c) for what value of c?

Answer 1

1 answer)

f(n)/g(n) converges to a positive value less than 1 as n tends to infinity when g(n) >f(n). It can be written as f(n)=O(g(n)).

Option c

2 answer)

In n+23 log(2n) , dominating term is n.

In worst case time complexity could be O(n) and not more than that.

Option b

3 answer)

f(n) is Ω(g(n)) when limn→∞ f(n)/g(n) >= 1.

Option b

4 answer)

It's trivial......f(n) is Θ(g(n)).

Option b

5 answer)

f(n)/g(n) converges to 0 as n tends to infinity when f(n)<g(n).

So option a.

6 answer)

In  T(n)=n^2+10n , major term is n^2. In worst case it can't be less than n^2.

So option e