# Number of time Statement Executed

• Oct 27th 2006, 06:56 PM
fifthrapiers
Number of time Statement Executed
From the following "pseudocodes", I have to determine how many times each statement

x <-- x + 1 is executed and explain why, from the following options:

O(1), O(log(n)), O(n), O(n*log(n)), O(n^2), O(n^3), O(2^n), or O(n!)

The pseudocode is the following (I don't recall how to do the indentations, but I think its just the "code" thing).

Code:

a.) for i <-- 1 to n     for j <-- 1 to n           for k <-- 1 to i               x <-- x + 1           next k     next j next i
Code:

b.) i <-- n while i >= 1     for j <-- 1 to n           x <-- x + 1     next j     i <-- [i/2] (square brackets without horizontal line at "top") end while
Code:

c.) i <-- 2 while i < n     i <-- i^2     x <-- x + 1 end while
Code:

d.) i <-- n while i >= 1     for j <-- 1 to i           x <-- x + 1     next j     i <-- [i/3] (square brackets without horizontal line at "top") end while
*EDIT*

Yay, [code] worked.
• Oct 28th 2006, 02:28 PM
CaptainBlack
Quote:

Originally Posted by fifthrapiers
From the following "pseudocodes", I have to determine how many times each statement

x <-- x + 1 is executed and explain why, from the following options:

O(1), O(log(n)), O(n), O(n*log(n)), O(n^2), O(n^3), O(2^n), or O(n!)

The pseudocode is the following (I don't recall how to do the indentations, but I think its just the "code" thing).

Code:

a.)   for i <-- 1 to n     for j <-- 1 to n           for k <-- 1 to i               x <-- x + 1           next k     next j next i

First check that the limits on the loops are what you intend.

1. The innermost loop has i assignments.

2. The next loop performs the inner loop n times, so with the inner loop
has n.i assgnments.

3. The outermost loop is performed for i=1..n, so the operations count
is:

$
\sum_{i=1}^n n\cdot i = n \sum_{i=1}^n i = n\ n(n+1)/2 = O(n^3)
$
• Oct 28th 2006, 02:54 PM
CaptainBlack
Quote:

Originally Posted by fifthrapiers
From the following "pseudocodes", I have to determine how many times each statement

x <-- x + 1 is executed and explain why, from the following options:

O(1), O(log(n)), O(n), O(n*log(n)), O(n^2), O(n^3), O(2^n), or O(n!)

The pseudocode is the following (I don't recall how to do the indentations, but I think its just the "code" thing).
Code:

b.)   i <-- n while i >= 1     for j <-- 1 to n           x <-- x + 1     next j     i <-- [i/2] // [.] floor function end while

1. The innermost loop has 1 assignment which is executed $n$ times.

2. The outer loop is executed $\lfloor \log_2(n) \rfloor$ times

3. Hence the total assignment count is:

$n\ \lfloor \log_2(n) \rfloor=O(n \log(n))$
• Nov 2nd 2006, 06:49 PM
fifthrapiers
Let me see if I can do c and d now.

For c:

1. The innermost loop has i assignments.

2. While x is less than n, there is 1 assignment.

Therefore, n*n = n^2 = O(n^2)

for d: This looks a lot like b.

1. The outer loop is executed log(n) times.

I think this one is similar to b, without the n scalar, so:

O(log(n)).
• Nov 2nd 2006, 11:28 PM
CaptainBlack
Quote:

Originally Posted by fifthrapiers
Let me see if I can do c and d now.

For c:

1. The innermost loop has i assignments.

2. While x is less than n, there is 1 assignment.

Therefore, n*n = n^2 = O(n^2)

Code:

c.) i <-- 2 while i < n   i <-- i^2   x <-- x + 1 end while
(I will assume that the while statement should be "while i<=n" as this
seems more natural to me than "while i<n", the changes needed if the latter
really is intended should be easy enough to make)

The loop has 1 assignment of the form x<--x+1, but how many trips
around this loop are there?

If n=2 or 3, then there is 1 trip, as i<--4 in the first trip and so
i is now >n and so no further trips will be made.

If n=4, 5, 6, 7, then there are two trips i<--8 after the second trip
and so is now greater than n so there will be no further trips.

In general if $n=2^k, 2^k+1, .. , 2^{k+1}-1$ there will be $\lfloor \log_2(n) \rfloor=k$
trips, which is $O(\log(n))$.

RonL
• Nov 2nd 2006, 11:44 PM
CaptainBlack
Quote:

Originally Posted by fifthrapiers
for d: This looks a lot like b.

1. The outer loop is executed log(n) times.

I think this one is similar to b, without the n scalar, so:

O(log(n)).

Except in b the inner loop had a trip count independent of the outer loop
count, here we have a decreasing trip count as the outer loop progresses.

I think we have a total trip count:

$
N \sim n+\lfloor n/3 \rfloor +\lfloor n/9 \rfloor + ... +\lfloor n/3^{\lfloor \log_3(n) \rfloor} \rfloor=O(n)
$

In this case I feel the need to actualy conduct an experiment to check this.
The attachment shows the result of this, and as the plot shows an essentialy straight line
I am reasonably happy that the result is OK.

RonL
• Nov 2nd 2006, 11:47 PM
fifthrapiers
Thanks a lot, CaptainBlack.