Name: _______________________________________

1

TCSS 343

Midterm exam (SIMULATION) Autumn 2020

1. Determine if the following relationships are True or False and justify the answers.

a. is Ω(1)

Solution: True by the limit test: lim

→∞

1

= ∞.

b. 33 + 22 + is (4)

Solution: True by the limit test: lim

→∞

33+22+

4

= lim

→∞

3

+ lim

→∞

2

2

+ lim

→∞

1

3

= 0.

c. √ is Θ(ln )

Solution: False by the limit test: lim

→∞

√

ln

= lim

→∞

1

2√

1

= lim

→∞

2√

= lim

→∞

√

2

= ∞.

2. Sort the following functions from slowest growth rate to fastest growth rate as a

sequence of six inequalities. Justify each consecutive pair with the limit test.

a. 5

b. 1 + ln(ln(ln ))

c. ln

d. ⋅ 2lg

Solution: after simplifying d: ⋅ 2lg = ⋅ = 2, it should become clear that:

b < c < d < a

Justifications of consecutive pairs:

b

1+ln(ln(ln ))

ln

= lim

→∞

1

ln

+ lim

→∞

ln(ln(ln ))

ln

= 0 + lim

→∞

1

ln(ln )

⋅

1

ln

⋅

1

1⋅ln +⋅

1

= lim

→∞

1

ln(ln )

⋅

1

ln

⋅

1

⋅

1

ln +1

= 0.

c

ln

2

= lim

→∞

ln

= lim

→∞

1

1

= lim

→∞

1

= 0.

d

2

5

= lim

→∞

1

3

= 0.

Name: _______________________________________

2

3. For each of the following pairs of functions, determine which relationship is true.

Relationship f(n) = O(g(n))? f(n)= (g(n))? f(n)= (g(n))?

f(n) = n2

g(n) = ln n2 + 5

False

True

False

f(n) = 10

g(n) = log 100

True

True

True

f(n) = (ln n)2

g(n) = n

True

False

False

Solution: by the limit test:

lim

→∞

2

ln 2+5

= lim

→∞

2

2

= lim

→∞

2 = ∞ hence ∈ Ω() in the 1st case;

lim

→∞

10

log 10

=

10

log 10

hence ∈ Θ() in the 2nd case;

lim

→∞

(ln )2

= lim

→∞

(2 ln )⋅

1

1

= lim

→∞

2 ln

= lim

→∞

2

1

= lim

→∞

2

= 0 hence ∈ O() in the 3rd case.

4. State and prove tight bounds on the following functions using a direct proof (from the

definition of Big Theta) or the limit test.

a. 53 + 22 + 12

Solution: Θ(3) by the limit test: lim

→∞

53+22+12

3

= lim

→∞

53

3

+ lim

→∞

22

3

+ lim

→∞

12

3

=

lim

→∞

5 + lim

→∞

2

+ lim

→∞

12

3

= 5 + 0 + 0 = 5.

b. (2 + 1)10

Solution: Θ(20) by the limit test: lim

→∞

(2+1)10

20

= lim

→∞

(

2+1

2

)

10

= lim

→∞

(1 +

1

2

)

10

=

(1 + 0)10 = 1.

c. log3

7

Solution: Θ(log ) by the limit test: lim

→∞

log3

7

log

= lim

→∞

7 log / log 3

log

= lim

→∞

7

log 3

=

7

log 3

.

5. Consider the following algorithm where [0. . − 1] is an array of integers:

1. for i = 0 to n – 2 do

2. sum = 0

3. for j = i + 1 to n – 1 do

4. sum = sum + A[j]

5. end for

6. if A[i] > sum / (n – i – 1) then

7. return false

8. end if

9. end for

10. return true

Name: _______________________________________

3

What is the Big Theta running time of this algorithm? Show and explain all your work.

Solution: Let denote the time needed to execute the instructions on line 4, let denote

the time needed to execute the instructions on lines 2 and 6–8 together, and let denote

the time needed to execute the instructions on line 10.

These are all constant (the number of instructions they represent doesn’t depend on the

value of , even though line 6 involves ).

However, the loop body on line 4 is executed once for each value of j, thus contributing

∑ −1=+1 = ( − 1 − ) to the running time.

Hence the loop body on lines 2–8 contributes ∑ {( − 1 − ) + }−2=0 = ∑

−2

=1 +

∑ {( − 1) + }−2=0 =

(−2)(−1)

2

+ (( − 1) + )( − 1) = (

3

2

) 2 + ( −

7

2

) + (2 −

).

The final contribution to the running time is from line 10.

Therefore, the overall running time is (

3

2

) 2 + ( −

7

2

) + (2 − + ), which is Θ(2)

by the limit test: lim

→∞

(

3

2

)2+(−

7

2

)+(2−+)

2

= lim

→∞

(

3

2

)2

2

+ lim

→∞

(−

7

2

)

2

+ lim

→∞

(2−+)

2

=

lim

→∞

(

3

2

) + lim

→∞

(−

7

2

)

+ lim

→∞

(2−+)

2

=

3

2

+ 0 + 0 =

3

2

.

6. Consider the following recurrence relation:

() = {

0, = 0

1, = 1

2( − 2) + 5, > 1

a. Use recursion trees or repeated substitution to guess that the tight bound for the

above recurrence relations is Θ(√2).

Solution: by repeated substitution, () = 2( − 2) + 5 = 2(2( − 2 − 2) + 5) + 5 =

22( − 2 ⋅ 2) + 5 ⋅ (2 + 1) = 22(2( − 2 ⋅ 2 − 2) + 5) + 5 ⋅ (2 + 1) = 22 ⋅ 2( − 2 ⋅

3) + 22 ⋅ 5 + 5 ⋅ (2 + 1) = 23( − 2 ⋅ 3) + 5 ⋅ (22 + 2 + 1) = ⋯ = 2( − 2 ⋅ ) + 5 ⋅

(2−1 + 2−2 + ⋯ + 2 + 1) = 2( − 2) + 5 ⋅ (2 − 1).

Now if is even, i.e. = 2 for some , then = /2 and () = 2( − 2) + 5 ⋅

(2 − 1) = 2/2(0) + 5 ⋅ 2/2 − 5 = 5 ⋅ √2 − 5.

Similarly, if is odd, i.e. = 2 + 1 for some , then = ( − 1)/2 and () =

2(−1)/2(1) + 5 ⋅ (2(−1)/2 − 1) = 2/2/√2 + 5 ⋅ 2/2/√2 − 5 = (3√2)2/2 − 5.

In either case one gets () ∈ Θ(√2) as the desired guess.

b. Use induction to prove the lower and upper bound.

Lower bound: one has to find constants , 0 > 0 such that (), as defined by the above

recurrence, satisfies () ≥ √2 for > 0.

Name: _______________________________________

4

Base cases: for = 0, () = (0) = 0 ≥ √20 = √2 , which is impossible to attain for

any > 0, hence one must take at least = 1, in which case () = (1) = 1 ≥ √21 =

√2 as long as ≤

1

√2

≈ 0.7. This value is good for the complementary base case = 2

(which is needed because even and odd numbers are kept separate by the definition of

()), because 5 = 2(0) + 5 = (2) ≥ √22 = 2, and hence ≤

5

2

.

Induction hypothesis: let > 1 , and assume that () , as defined by the above

recurrence, satisfies () ≥ √2 for any 1 ≤ < and some constant .

Inductive step: let > 1 . From the recurrence one has () = 2( − 2) + 5 , and

together with the induction hypothesis this yields () = 2( − 2) + 5 ≥ 2√2−2 + 5 =

√2 + 5 > √2, which holds for any > 0.

Combining the restriction of the base cases, one concludes that () ≥ √2 for =

1

√2

>

0 and > 0 = 1 > 0.

Upper bound: one has to find constants , 0 > 0 such that (), as defined by the above

recurrence, satisfies () ≤ √2 for > 0.

Base cases: 0 = (0) ≤ √20 holds for all ≥ 0, 1 = (1) ≤ √21 holds for all ≥

1

√2

,

hence one needs ≥

1

√2

to cover both bases cases.

Induction hypothesis ( > 1): () ≤ √2 for 1 ≤ < .

Inductive step ( > 1): () = 2( − 2) + 5 ≤ 2√2−2 + 5 = √2 + 5.

Combining the restriction of the base cases, one concludes that () ≤ √2 for =

1

√2

>

0 and > 0 = 1 > 0. □

7. Which of the following recurrences cannot be solved using the Master Theorem?

a. () = (

) + (coefficient is not a constant)

b. () = (

3

) +

c. () =

(

) + (coefficient is not ≥ 1)

d. () = 4 (

3

) +

e. () = (

) + (coefficient is not > 1)

f. () = 9 (

3

) + / log

g. () = (

) + / (none of the cases apply)

8. Use the Master Theorem to give tight asymptotic bounds for the following recurrences,

where (1) = in all cases.

a. () = 4 (

2

) +

Name: _______________________________________

5

Solution:

We have = 4, = 2, log = log2 4 = 2 and () = . Then () = ∈ (

log −) =

(2−) for any 0 < < 1 by the limit test and Case 1 applies. Therefore () ∈ Θ(2).

b. () = 4 (

2

) + 2.

Solution:

We have = 4, = 2, log = log2 4 = 2 and () =

2. Then () = 2 ∈ Θ(log ) =

Θ(2) by the limit test and Case 2 applies. Therefore () ∈ Θ(2 log ).

c. () = 4 (

2

) + 3.

Solution:

We have = 4 , = 2 , log = log2 4 = 2 and () =

3 . Then () = 3 ∈

Ω(log +) = Ω(2+) for any 0 < < 1 by the limit test. Furthermore, (/) =

4(/2)3 = (1/2)3 = (1/2)() and hence (/) < () where 0 < = 1/2 < 1 .

Thus Case 3 applies. Therefore () ∈ Θ(3).

d. () = 4 (

2

) + 2 log3 .

Solution:

We have = 4, = 2, log = log2 4 = 2 and () =

2 log3 . Then () = 2 log3 ∈

Θ(log log3 ) = Θ(2 log3 ) by the limit test and the extension to Case 2 applies.

Therefore () ∈ Θ(2 log3+1 ) = Θ(2 log4 ).

欢迎咨询51作业君