(note: I know the answer for the first one is (lg lg n), I really just want to k

Question

(note: I know the answer for the first one is (lg lg n), I really just want to know how to solve for the answer...also we have not learned about alternating series and are in cs191, )

1. (10 pts)4.3.26 Find a theta notation for the number of times the statement x = x + 1 is executed.

1. i = 2

2. while (i < n){

3.            i = i^2

4.            x = x + 1

5. }

2. (10 pts)4.3.27 Let t(n) be the total number of times that i is incremented and j is decremented in the following pseudocode, where a1, a2, . . . is a sequence of real numbers.

1. i = 1

2. j = n

3. while (i < j){

4.    while (i < j ai < 0)

5.         i = i + 1

6.    while (i < j ai 0)

7.         j = j 1

8.    if (i < j)

9.         swap(ai , aj ) j = j 1

10. }

Find a theta notation for t(n)

The following are the possible answers:

(1)

(lg lg n)

(lg n)

(n)

(n lg n)

(n^2)

(n^3)

(2^n)

(n!)

Explanation / Answer

1)

i = 2

2. while (i < n){

3.            i = i^2

4.            x = x + 1

5. }

We begin by simply observing the pattern of values of i as we iterate the while loop, forgetting momentarily about n .
The pattern starts as follows: 2,4,16,256,. . .Writing this as powers of 2 we see the pattern 2^1->2^2->2^4->2^8 = 2^16->. . That is, after the first iteration i = 2^21 , after the second i = 2 2 2 , after the third i = 2 2 3 , and so on. By an easy induction
one sees that after the k th iteration we must have i = 2^2^k . So now let n be an integer > 2, and let f(n) denote the number of times.
the statement x := x + 1 is executed. Now there exists a unique positive integer k with 2 2 k - 1 < n = 2 2 k .
we see that the while loop will iter ate exactly k times before terminating, and during each iteration the statement x := x +1 is executed once. Therefore f (n) = (lg lg n)

2)

1. i = 1

2. j = n

3. while (i < j){

4.    while (i < j ai < 0)

5.         i = i + 1

6.    while (i < j ai 0)

7.         j = j 1

8.    if (i < j)

9.         swap(ai , aj ) j = j 1

10. }

Let f (n) denote the number of times x := x + 1 is executed. Observe first that f (n) = n , because the first iteration of the while loop contains a for l oop from i = 1 to n , meaning that x := x + 1 is executed n times during this first iteration. Hence f (n) = ?(n). We claim that f (n) = O(n). To see this, let n k denote the value of j at the end to the k th iteration of the while loop.

f (n) = O(n)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.