Asymptotic running time of code segments

[GeorgeCostanz]

I'm trying to grasp some basic concepts of analyzing code segments. Not sure if I have the right thought process. Can't find many examples online.

Homework Statement

A.)
for (i=1; i<n; i++)
for (j=1; j<n; j++)
return 1

Guess: Theta(n) because both loops go to (n) and they're independent? or is it constant because it's only doing a constant bit of work?

B.)
for (i=1; i<n; i++)
for (j=1; j<log n; j++)
A[j] = 3A[j]

Guess: Theta(n) because the outer loop goes to (n)?

C.)
for (i=1; i<5; i++)
for (j=1; j<i; j++)
A[j] = 0

Guess: Theta(1) because it executes in constant time?

D.)
for (i=1; i<5; i++)
for (j=1; j<i; j++)
i = n

Guess: Theta(1) because it executes in constant time?

E.)
x = n
while (x > 1)
x = x/2

Not sure how to do this

F.)
x = 1
while (x<n)
x = x+3

Not sure how to do this either.

Homework Equations

3. The Attempt at a Solution [/B]

I put the attempts in part 1 because it's easier to follow. Any help would be appreciated, thanks.

 

[Mark44]

I'm trying to grasp some basic concepts of analyzing code segments. Not sure if I have the right thought process. Can't find many examples online.

Homework Statement

A.)
for (i=1; i<n; i++)
for (j=1; j<n; j++)
return 1

Is this C code? If so, you're missing a semicolon on the return statement. Also, in the code I copied I see some indentation that doesn't show up in your first post. When you post code, please put a [ code ] tag at the top of it, and a [ /code ] tag at the bottom, without the extra spaces that I showed. That will preserve your indentation. I have put your first example in the code tags, and I have also added a semicolon in the return statement.

for (i=1; i<n; i++)
    for (j=1; j<n; j++)
     return 1;

The real question is how many times does the inner loop body run?

Guess: Theta(n) because both loops go to (n) and they're independent? or is it constant because it's only doing a constant bit of work?

B.)
for (i=1; i<n; i++)
for (j=1; j<log n; j++)
A[j] = 3A[j]

Guess: Theta(n) because the outer loop goes to (n)?

C.)
for (i=1; i<5; i++)
for (j=1; j<i; j++)
A[j] = 0

Guess: Theta(1) because it executes in constant time?

D.)
for (i=1; i<5; i++)
for (j=1; j<i; j++)
i = n

Guess: Theta(1) because it executes in constant time?

E.)
x = n
while (x > 1)
x = x/2

Not sure how to do this

F.)
x = 1
while (x<n)
x = x+3

Not sure how to do this either.

Homework Equations

3. The Attempt at a Solution [/B]

I put the attempts in part 1 because it's easier to follow. Any help would be appreciated, thanks.

 

[STEMucator]

With the code modifications Mark suggested in his post, the code in part A) should properly run. The fact the return statement is inside the inner loop means the code will execute in $O(1)$ time (due to early exit). Pretending the return statement isn't there though will yield a much more interesting result. Suppose the code reads:

for (i=1; i<n; i++)
    for (j=1; j<n; j++)

When the first iteration for $i$ occurs, you know the inner $j$ loop will execute until $j < n$. This results in a $O(n-1) = O(n)$ run time for the inner loop since $j$ began at one (hence the inner loop executes $n-1$ times).

The second iteration for $i$ will then occur, and the inner $j$ loop will once again execute. Again this results in $O(n-1) = O(n)$ run time for the inner loop.

This means by the time the outer loop executes $n-1$ times, the code will have taken $O(n^2)$ time to have run.

Proof: $T(n) = (n - 1)*(n-1) = n^2 - 2n + 1 \leq n^2 + 1 \leq 2n^2$ for $n \geq 1$.

Hence $T(n) \leq 2n^2 = kf(n)$. So you could conclude $T(n) = O(n^2)$.

I hope this example will help with your other code snippets.

EDIT: I forgot to mention something if you were looking for $\Theta$ of the code run time. The code will execute in $\Omega(n^2)$ time at best.

Since it executes with the same efficiency in the best and worst case scenario (i.e $T(n) = O(n^2) = \Omega(n^2)$), it can be concluded $T(n) = \Theta(n^2)$.

 

[STEMucator]

Part E) and F) are good examples even though they have $while$ loops instead.

For $E)$ I think you are meant to assume that $x$ is of type $float \space / \space double$, otherwise the code would not be very interesting (integer division is a problem).

You need to consider what happens when $n \leq 2$. This is quite trivial and produces an expected $T(n) = \Omega(1)$ at best.

If $n \geq 3$ you can start getting an upper bound on the code. It's clear to see that $\Theta$ will not be definable since $\Omega(1) \neq O(?)$.

 

[GeorgeCostanz]

It's actually supposed to be "pseudo-code". Appreciate the help guys

So for B, would it be theta (n) because the outer loop dominates? And C is theta(1)?

but for D, how could we answer this if we don't know what 'n' will be? Everything I posted is everything I was given in the question

 

[Mark44]

Part E) and F) are good examples even though they have $while$ loops instead.

For $E)$ I think you are meant to assume that $x$ is of type $float \space / \space double$, otherwise the code would not be very interesting (integer division is a problem).

How is integer division a problem?

You need to consider what happens when $n \leq 2$. This is quite trivial and produces an expected $T(n) = \Omega(1)$ at best.

If $n \geq 3$ you can start getting an upper bound on the code. It's clear to see that $\Theta$ will not be definable since $\Omega(1) \neq O(?)$.

 

[STEMucator]

How is integer division a problem?

If $n = 3$, then on the first iteration $x$ will get set to $3/2 = 1.5$. If $x$ is an int, then the $0.5$ will be truncated, and $x = 1$. This is a different result than what I think was intended.

Continuing the pattern using a precision type, you would expect $O(\frac{n}{2})$.

 

[Mark44]

If $n = 3$, then on the first iteration $x$ will get set to $3/2 = 1.5$. If $x$ is an int, then the $0.5$ will be truncated,

That's not how integer division works. Using integer division, 3/2 == 1. There is no fractional part, so no fractional part gets truncated.

and $x = 1$. This is a different result than what I think was intended.

Continuing the pattern using a precision type, you would expect $O(\frac{n}{2})$.

Which is what you get with either type of division. My point is that raising a question of which type of division is being performed is irrelevant, not to mention that the OP tells us that this is pseudocode, so fine points of integer division vs. floating point division aren't germane to the discussion.

 

[STEMucator]

That's not how integer division works. Using integer division, 3/2 == 1. There is no fractional part, so no fractional part gets truncated.

Which is what you get with either type of division. My point is that raising a question of which type of division is being performed is irrelevant, not to mention that the OP tells us that this is pseudocode, so fine points of integer division vs. floating point division aren't germane to the discussion.

I disagree entirely.

For $n == 3$, you would expect two iterations. One for 3 and one for 1.5, but if $x$ is an int, you're only going to get one iteration, namely for 3.

For $n == 4$, you obviously know two iterations will happen, and that works fine either way.

For $n == 5$, you expect three iterations. One for 5, 2.5 and 1.25 respectively. If $x$ is an int, you're only going to get an iteration for 5 and 2 respectively.

For $n == 6$, same deal as $n == 4$. You expect three iterations.

For $n == 7$, you expect three iterations for 7, 3.5, 1.75. If $x$ is an int, you get an iteration for 7 and 3.

For $n == 9$, you expect four iterations for 9, 4.5, 2.25, 1.125. If $x$ is an int, then you only iterate for 9, 4, 2.

Clearly whether or not $x$ is an int is significant to the outcome.

Although I agree if the code is pseudo code, specifics like these shouldn't matter too much. I just felt as if it's relevant to the understanding.

 

[Mark44]

I disagree entirely.

For $n == 3$, you would expect two iterations. One for 3 and one for 1.5, but if $x$ is an int, you're only going to get one iteration, namely for 3.

For $n == 4$, you obviously know two iterations will happen, and that works fine either way.

For $n == 5$, you expect three iterations. One for 5, 2.5 and 1.25 respectively. If $x$ is an int, you're only going to get an iteration for 5 and 2 respectively.

For $n == 6$, same deal as $n == 4$. You expect three iterations.

For $n == 7$, you expect three iterations for 7, 3.5, 1.75. If $x$ is an int, you get an iteration for 7 and 3.

For $n == 9$, you expect four iterations for 9, 4.5, 2.25, 1.125. If $x$ is an int, then you only iterate for 9, 4, 2.

Clearly whether or not $x$ is an int is significant to the outcome.

Although I agree if the code is pseudo code, specifics like these shouldn't matter too much. I just felt as if it's relevant to the understanding.

I think you're missing the point of the exercise, which is to analyze the time behavior of the loops, in general, not for specific small values of n. Since the examples are given in pseudocode, it's not reasonable to assume that division follows rules that are peculiar to programming languages that are derived from C. The whole business of how division is performed is a red herring, IMO.

 

[GeorgeCostanz]

lol