# Math Help - Number of time Statement Executed

1. ## 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.

2. 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)
$

3. 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))$

4. 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)).

5. 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

6. 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

7. Thanks a lot, CaptainBlack.