# Determining the big-O runtimes of these different loops?

I have a series of questions in which I need feedback and answers. I will comment as to what I think, this is not a homework assignment but rather preparation for my exam.

My main problem is determining the iterations of a loop for different cases. How would go about attempting to figure that out?

Evaluate Running time.

Q2.

`````` for(int i =0 ; i < =n ; i++) // runs n times
for(int j =1; j<= i * i; j++) // same reasoning as 1. n^2
if (j % i == 0)
for(int k = 0; k<j; k++) // runs n^2 times? <- same reasoning as above.
sum++;
``````

Correct Answer: N × N2 × N = O(N^4)

For the following Questions below, I do not have the correct answers.

Q3. a)

``````     int x=0; //constant
for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
x=x+2*i;
``````

b) Assume for simplicity that n = 3^k

``````    int z=0;
int x=0;
for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
z = z+5;
z++;
x = 2*x;
}
``````

c) Assume for simplicity that n = k^2,

``````   int y=0;
for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
y++; //constant
``````

d)

``````  int b=0; //constant
for(int i=n; i>0; i--) //n times
for(int j=0; j<i; j++) // runs n+ n-1 +...+ 1. O(n^2)
b=b+5;
``````

(e)

`````` int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs n times
y=y+i;
int s=0;
for(i=1; i<=j; i++) // runs n times
s++;
``````

(f)

`````` int b=0;
for(int i=0; i<n; i++) //runs n times
for(int j=0; j<i*n; j++) //runs n^2 x n times?
b=b+5;
``````

(g) Assume for simplicity that n = 3k, for some positive integer k.

``````   int x=0;
for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i.
if(i%2 != 0) //will always be true for values above
for(int j=0; j<i; j++) // runs n times
x++;
}
``````

My Answer: O (n x log base 3 n? )

(h) Assume for simplicity that n = k2, for some positive integer k.

``````   int t=0;
for(int i=1; i<=n; i++) //runs n times
for(int j=0; j*j<4*n; j++) //runs O(logn)
for(int k=1; k*k<=9*n; k++) //runs O(logn)
t++;
``````

My Answer: n x logn x log n = O(n log n^2)

(i) Assume for simplicity that n = 2s, for some positive integer s.

``````   int a = 0;
int k = n*n;
while(k > 1) //runs n^2
{
for (int j=0; j<n*n; j++) //runs n^2
{ a++; }
k = k/2;
}
``````

(j)

``````  int i=0, j=0, y=0, s=0;
for(j=0; j<n+1; j++) //runs n times
y=y+j; //y equals n(n+1)/2 ~ O(n^2)
for(i=1; i<=y; i++) // runs n^2 times
s++;
``````

(k) int i=1, z=0; while( z < n*(n+1)/2 ){ //arithmetic series, runs n times z+=i; i++; }

(m) Assume for simplicity that n = 2s, for some positive integer s.

``````  int a = 0;
int k = n*n*n;
while(k > 1) //runs O(logn) complexity
{
for (int j=0; j<k; j++) //runs n^3 times
{ a--; }
k = k/2;
}
``````

Question 4

• a) True - since its bounded below by n^2
• b) False - f(n) not strictly smaller than g(n)
• c) True
• d) True -bounded by n^10
• e) False - f(n) not strictly smaller than g(n)
• f) True
• g) True
• h) false - since does not equal O(nlogn)
• i) true
• j) not sure
• k) not sure
• l) not sure - how should i even attempt these?*

• Did you consult a book? Some of these are the most basic cases for analysis. Jun 19 '12 at 4:26
• When you calculate the run time of an inner loop to be n^2 you have already taken into account the time efficiency of the outer loop. So you don't multiply it by the outer-loops efficiency at the end of the problem...that's extreme double-counting. Jun 19 '12 at 4:28
• A good generalization is that if you have three nested loops running i, j, and k times, respectively -- you have efficiency O(ijk). If you think about this, using the same logic, two nested loops running n times each gives you O(n*n) = O(n^2). With the n-1 cases etc, you can just estimate it as n -- big O is an upper bound Jun 19 '12 at 4:30
• Q2) wtf? `i=i++` and `i * i, j++`(the comma)
– goat
Jun 19 '12 at 4:48
• `for(int i =0 ; i < =n ; i++) // runs n times` wrong: runs n+1 times Jun 19 '12 at 16:10

Let's go through these one at a time.

## Part (a)

`````` int x=0; //constant
for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
x=x+2*i;
``````

Yep! That's correct. The loop runs O(n) times and does O(1) work per iteration.

## Part (b)

``````int z=0;
int x=0;
for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
z = z+5;
z++;
x = 2*x;
}
``````

Not quite. Think about the values of `i` as the loop progresses. It will take on the series of values 1, 3, 9, 27, 81, 243, ..., 3k. Since `i` is tripling on each iteration, it takes on successive powers of three.

The loop clearly only does O(1) work per iteration, so the main question here is how many total iterations there will be. The loop will stop when `i` > `n`. If we let `k` be some arbitrary iteration of the loop, the value of `i` on iteration `k` will be 3k. The loop stops when 3k > n, which happens when k > log3 n. Therefore, the number of iterations is only O(log n), so the total complexity is O(log n).

## Part (c)

``````int y=0;
for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
y++; //constant
``````

Not quite. Notice that `j` is still growing linearly, but the loop runs as long as j2 ≤ n. This means that as soon as j exceeds √ n, the loop will stop. Therefore, there will only be O(√n) iterations of the loop, and since each one does O(1) work, the total work done is O(√n).

## Part (d)

``````int b=0; //constant
for(int i=n; i>0; i--) //n times
for(int j=0; j<i; j++) // runs n+ n-1 +...+ 1. O(n^2)
b=b+5;
``````

Not quite. You're actually doubly-counting a lot of the work you need to do. You're correct that the inner loop will run n + (n-1) + (n-2) + ... + 1 times, which is O(n2) times, but you're already summing up across all iterations of the outer loop. You don't need to multiply that value by O(n) one more time. The most accurate answer would be O(n2).

## Part (e)

``````int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs n times
y=y+i;

int s=0;
for(i=1; i<=j; i++) // runs n times
s++;
``````

Yep! Exactly right.

## Part (f)

``````int b=0;
for(int i=0; i<n; i++) //runs n times
for(int j=0; j<i*n; j++) //runs n^2 x n times?
b=b+5;
``````

Again, I believe you're overcounting. The inner loop will run 0 + n + 2n + 3n + 4n + ... + n(n-1) = n(0 + 1 + 2 + ... + n - 1) times, so the total work done is O(n3). You shouldn't multiply by the number of times the outer loop runs because you're already summing up across all iterations. The most accurate runtime would be O(n3).

## Part (g)

``````int x=0;
for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i.
if(i%2 != 0) //will always be true for values above
for(int j=0; j<i; j++) // runs n times
x++;
}
``````

My Answer: O (n x log base 3 n? )

The outer loop here will indeed run O(log n) times, but let's see how much work the inner loop does. You're correct that the `if` statement always evaluates to true. This means that the inner loop will do 1 + 3 + 9 + 27 + ... + 3log3 n work. This summation, however, works out to (3log3 n + 1 - 1) / 2 = (3n + 1) / 2. Therefore, the total work done here is just O(n).

## Part (h)

``````int t=0;
for(int i=1; i<=n; i++) //runs n times
for(int j=0; j*j<4*n; j++) //runs O(logn)
for(int k=1; k*k<=9*n; k++) //runs O(logn)
t++;
``````

My Answer: n x logn x log n = O(n log n^2)

Not quite. Look at the second loop. This actually runs O(√n) times using the same logic as one of the earlier parts. That third inner loop also runs O(√n) times, and so the total work done will be O(n2).

## Part (i)

``````int a = 0;
int k = n*n;
while(k > 1) //runs n^2
{
for (int j=0; j<n*n; j++) //runs n^2
{ a++; }
k = k/2;
}
``````

Not quite. The outer loop starts with k initialized to n2, but notice that k is halved on each iteration. This means that the number of iterations of the outer loop will be log (n2) = 2 log n = O(log n), so the outer loop runs only O(log n) times. That inner loop does do O(n2) work, so the total runtime is O(n2 log n).

## Part (j)

``````int i=0, j=0, y=0, s=0;
for(j=0; j<n+1; j++) //runs n times
y=y+j; //y equals n(n+1)/2 ~ O(n^2)
for(i=1; i<=y; i++) // runs n^2 times
s++;
``````

Close, but not quite! The first loop runs in time O(n) and by the time it's done, the value of j is Θ(n2). This means that the second loop runs for time Θ(n2), so the total time spent is Θ(n2).

## Part (k)

`````` int i=1, z=0;
while( z < n*(n+1)/2 )//arithmetic series, runs n times
{
z+=i; i++;
}
``````

That's correct!

## Part (l)

That's odd, there is no part (l).

## Part (m)

``````int a = 0;
int k = n*n*n;
while(k > 1) //runs O(logn) complexity
{
for (int j=0; j<k; j++) //runs n^3 times
{ a--; }
k = k/2;
}
``````

Close, but not quite. You're right that the outer loop runs O(log n) times and that the inner loop does O(n3) work on the first iteration. However, look at the number of iterations of the inner loop more closely:

n3 + n3 / 2+ n3 / 4 + n3 / 8 + ...

= n3 (1 + 1/2 + 1/4 + 1/8 + ...)

≤ 2n3

So the total work done here is actually only O(n3), even though there are log n iterations.

# Question 4

f) True

This is actually false. The expression on the left is

(3/2)n3/2 + 5n2 + lg n

which is not Ω(n2 √n) = Ω(n5/2)

For (j), note that log n6 = 6 log n. Does that help?

For (k), ask whether both sides are O and Ω of one another. What do you find?

For (l), use the fact that alogb c = clogba. Does that help?

Hope this helps!

• shouldn't part (f) be O(n^2) as the outer loop runs n times and inner loop runs n because 0+n+2n+3n+...+nx(x+1)/2 = n(1+2+3+.....x(x+1)/2) so total is O(n^2) Feb 11 '16 at 0:06
• The way I see it, the first iteration of the inner loop runs 0 times, the second n times, the third 2n times, etc. That means that the total work done is 0 + n + 2n + 3n + ... + (n-1)n = n(0 + 1 + 2 + ... + n-1). This is n(n-1)n / 2 = Theta(n^3). Is there something wrong with my reasoning? Feb 11 '16 at 0:52
• It just looks like 0+n+2n+.... is a mathematical series that's equivalent to the result I posted above.. I'm not sure about (n-1)n? Feb 11 '16 at 1:23
• 0 + 1 + 2 + ... + n-1 is n(n-1)/2, so 0n + 1n + 2n + ... + (n-1)n = (0+1+2+...+n-1)n = n(n-1)n/2. Is that incorrect? Also, I think your series is wrong - the last term should be n(n-1) rather than nx(x +1)/2. I don't think I see what x is here. Feb 11 '16 at 1:34
• @Garrick Great catch! Fixed. Aug 2 '17 at 13:14
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}