COS226 Analysis of Algorithms: Practice Examples Spring ‘20

Overview. This worksheet has worked examples for the running time analysis of small pieces of code, by
counting the number of performed operations.

To get the full benefit, go through the examples in the same order they are presented and avoid looking at the
solutions and explanations until you have tried to find the running time on your own.
You will find at the end of the worksheet a summary of basic summations and logarithms rules, which are
helpful when analyzing running times for simple pieces of code.

Question. For each of the following pieces of code, find the number of times op() is called as a function of the
input size n. Express your answer in terms of the Big-Theta notation.

Single Loops
Ex.1
for (i = 10; i < n + 5; i += 2)
Solution. Θ(n).
op(); op() is called exactly (n + 5 − 10)/2 times.

Ex.2 Solution. Θ(log n).

for (i = 1; i < n; i *= 2)
op(); The number of steps needed to get from 1 to n by
doubling or from n to 1 by halving is log2 n.
for (i = n; i > 1; i /= 2) The base is not important when using the order of
op(); growth notation, since logs with different bases are
a constant factor away from each other.
(See A.6 in the Math Cheat Sheet at the end).

Ex.3 for (i = 10; i < n + 5; i *= 3) Solution. Θ(log n).

op(); The loop will multiply i = 10 by 3 until
n +5
10 × 3i ≥ n + 5. Solving for i, we get i = log3 .
10

Ex.4
for (i = 0; i < n * n * n; i *= 2)
Solution. Θ(log n).
op(); log2 n 3 = 3 log2 n. We can drop the coefficient and
ignore the base.

Ex.5 for (i = 0; i * i < n; i++) Solution. Θ( n).

op();
This is because n× n = n.
 COS226 Analysis of Algorithms: Practice Examples Spring ‘20

Nested Independent Loops

Ex.6
for (i = 10; i < n; i++)
Solution. Θ(n 2 ).
for (j = 0; j < n; j += 2) n 1
op() is called exactly (n − 10) × = n 2 − 5n
op(); 2 2

times.

Ex.7 for (i = 0; i < n; i++) Solution. Θ(n).

for (j = 0; j < 100; j++) op() is called 100n times, but we ignore the
op();
coefficient.

Ex.8
for (i = 0; i < n; i++) { Solution. Θ(n 2 ).
for (j = 0; j < n; j++) At each iteration of the outer loop, the first inner
op(); loop runs and then the second inner loop runs.
for (j = 1; j < n; j *= 2); Therefore, op() is called n × (n + log n)
op(); = n 2 + n log n times, which is in the order of n 2.
}

Nested Dependent Loops

Ex.9 for (i = 1; i <= n; i++) Solution. Θ(n 2 ).

for (j = 1; j <= i; j ++) The inner loop performs 1 iteration when
op();
i = 1, and 2 iterations when i = 2, etc.
Therefore, op() is called 1 + 2 + … + n times. This can be represented as a summation:
n
n(n + 1)
∑
i= Eq. 1
i=0
2

Explanation. To understand why Eq. 1 is true, note that if we add the numbers twice, we get:

0 + 1 + … + (n − 1) + n
+ n + (n − 1) + … + 1 + 0
= n + n + … + n + n n +1 terms

In other words, 2 × (0 + 1 + … + n) = n × (n + 1), which can be re-organized to give Eq. 1

We can also think of this visually as follows: How many blue circles for n = 4?
n rows and n + 1 columns
area = n × (n + 1)
1
blue circles = × n × (n + 1)
2
 COS226 Analysis of Algorithms: Practice Examples Spring ‘20

Ex.10 Solution. Θ(n 4 ).

for (i = 1; i <= n * n - 10; i++)
for (j = 1; j <= i; j ++) The inner loop performs 1 iteration when
op(m); i = 1, and 2 iterations when i = 2, etc.

Therefore, op() is performed 1 + 2 + … + (n 2 − 10) times. This can be represented as a summation:

n 2 −10
(n 2 − 10) × ((n 2 − 10) + 1)
∑
i , which equals to = (using Eq. 1)
i=0
2

Simplifying the result and dropping the coefficients and lower order terms leads to n 4.

Ex.11 Solution. Θ(n 3).

for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++) When i = 1, op() is performed 1 × 1 times, when
for (k = 1; k <= i; k++) i=2, op() is performed 2 × 2 times, etc. Hence
op(); the total number of times op() is performed is:

n
1
12 + 22 + 32 + … + n 2 = i2 ∼ n3
∑
Eq. 2
3
i=1

Explanation.
To understand why this summation is in the order of n 3, consider the following two observations:

1. Upper bound: 12 + 22 + … + n 2
≤ n2 + n2 + … + n2
≤ n × n2
Therefore, the order of growth is not more than n 3 .

Considering only the 2nd

n n
2. Lower bound: 12 + 22 + … + n 2 ≥ ( 2 )2 + (( 2 + 1)2 ) + … + n 2 half of the summation.
≥ ( n2 )2 + ( n2 )2 + … + ( n2 )2
n
≥ 2
× ( n2 )2

1
Therefore, the order of growth is not less than 8
n 3.

Since we drop constant coefficients, the upper and lower bounds imply that the order of growth is n 3.

See B.6 in the math cheat sheet for the exact closed form of this summation.
 COS226 Analysis of Algorithms: Practice Examples Spring ‘20

Ex.12 Solution. Θ(n 3).

for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++) op() is called 1 time when j = 1, 2 times when
for (k = 1; k <= j; k++) i

∑
op(); j = 2, etc. Therefore, op() is called j times.
j=1

However, i takes all the values from 1 → n. Therefore, the total number of times op() is called is:
n i n
i(i + 1)
∑∑ ∑
j= (using Eq. 1)
i=1 j=1 i=1
2

n n n
1 2 1 1
i 2+ 1
∑ ∑ ∑
= i + i = i
2 2 2 2
i=1 i=1 i=1
n
1
i 2, which is in the order of n 3 (using Eq. 2).
∑
Dropping lower order terms, we are left with
2
i=1

Ex.13 for (i = 1; i <= n; i *= 2) Solution. Θ(n).

for (j = 1; j <= i; j++) The inner loop performs 1 iteration when
op();
i = 1, and 2 iterations when i = 2, etc.
Therefore, op() is called 1 + 2 + 4 + … + n times, because i doubles in each iteration of the outer
loop. This equals to 20 + 21 + … + 2k, where 2k = n and can be represented as a summation:
lg n
2k = 2lg n+1 − 1 ∼ 2n
∑ Eq. 3
k=0

Using the identity a m × a n = a m+n, we can represent the answer as 21 × 2lg n − 1

Using the identity x lg y = y lg x, we can represent the answer as 21 × n lg 2 − 1 = 21 × n 1 − 1,
which is in the order of n.
Explanation.
This is a geometric sum that can be calculated using the geometric sum formula:
m
r m+1 − 1
ri =
∑ r −1
Eq. 4
i=0

where m = lg n and r = 2 in this exercise. The following is a visual explanation for this special case:

20
20 21
0
2 21 22
21 = 22 − 1 22 = 23 − 1 23 = 24 − 1
3 7 15
 COS226 Analysis of Algorithms: Practice Examples Spring ‘20

Ex.14 Solution. Θ(n log n).

for (i = 1; i <= n; i++)
for (j = 1; j < i; j *= 2) The inner loop performs lg 1 iterations when
op(); i = 1, and lg 2 iterations when i = 2, etc.

Therefore, op() is called lg 1 + lg 2 + … + lg n times. Using the identity log(a b) = log a + log b, we
can rewrite the summation as: lg 1 + lg 2 + … + lg n = lg(1 × 2 × . . . × n) = lg(n!).
Using Stirling’s Approximation:
lg(n!) ∼ n lg n Eq. 5

Ex.15 for (i = 1; i <= n; i++) Solution. Θ(n log n).

n
for (j = 1; j <= n; j += i) The inner loop performs 1
iterations when
op(); n
i = 1, and 2
iterations when i = 2, etc.
n n n
Therefore, op() is called + +…+ , which can be represented as the summation:
1 2 n
n n
n 1
∑i ∑i
=n×
i=1 i=1

This is n multiplied by a Harmonic Number. Harmonic numbers can be approximated by turning the
summation into an integral:
n n
1 1
∑i ∫1 i
∼ di = ln n Eq. 6
i=1

Hence, the total is ∼ n ln n.

Ex.16 Solution. Θ(n 2 ).

for (i = 1; i <= n; i++) { There are two independent inner loops:
for (j = 1; j <= n; j += i)
op(); • The first inner loop combined with the outer
loop are identical to the one in Ex.15, which
for (j = 1; j <= i; j++)
op(); runs in the order of n log n.
}
• The second inner loop combined with the
outer loop are identical the one in Ex.9, which
runs in the order of n 2.
The total is n log n + n 2, which is order n 2.
 COS226 Analysis of Algorithms: Practice Examples Spring ‘20

Recursive Algorithms

Ex.17 Solution. Θ(n).

void f(int n) {
if (n == 0) return; op() is executed once in each of the
op(); recursive calls for n, n − 1, …, 2, 1.
f(n-1); These are exactly n calls.
}

Ex.18 Solution. Θ(log n).

void f(int n) {
if (n == 1) return; op() is executed once in each of the
n n
op(); recursive calls for n, , , …, 2, 1.
f(n/2); 2 4
} These are lg n calls.

Ex.19 Solution. Θ(n 2 ).

void f(int n) {
if (n == 0) return; op() is executed n times for f(n) and n − 1
for (int i = 0; i < n; i++) times for f(n-1), etc. This means that op() is
op(); executed n + (n − 1) + … + 1 times.
f(n-1); From Eq. 1, we know this is in the order of n 2.
}

Ex.20 Solution. Θ(n).

void f(int n) { n
if (n == 0) return; op() is executed n times for f(n) and times
2
for (int i = 0; i < n; i++) for f(n/2), etc. This means that op() is
op(); n n
executed n + + + … + 1 times. This can be
f(n/2); 2 4
} 1 1 1
written as n × (1+ 2 + 4 +…+ n ), which is in the
order of n (See B.8 in the cheat sheet at the end).

Ex.21
void f(int n) {
Solution. Θ(n).
if (n == 0) return; Consider the following visualization for the
op(); recursive calls:
f(n/2);
f(n/2);
}
f(n) 20 op() calls

f( n2 ) f( n2 ) 21 op() calls
op() is performed once in each recursive call.
The total number of calls to op() is
f( n4 ) f( n4 ) f( n4 ) f( n4 ) 22 op() calls
0 1 2 lg n
2 +2 +2 +…+2 , which is in the order of n …
(see Eq.3).
f( nn ) f( nn ) 2lg n op() calls
 COS226 Analysis of Algorithms: Practice Examples Spring ‘20

Ex.22 Solution. Θ(2n ).

void f(int n) {
if (n == 0) return; As in Ex.21, f(n) produces a binary tree, but with
op(); n + 1 levels instead of lg n + 1 levels. Since op() is
f(n-1); performed once in each recursive call, the total
f(n-1); number of times op() is performed is:
} 20 + 21 + 22 + … + 2n.
From Eq.4, we know this is 2n+1 − 1 = 21 × 2n − 1,
which is in the order of 2n.

Ex.23
void f(int n) {
Solution. Θ(n lg n).
if (n == 0) return; In each call to f(n), op() is performed a number of
for (int i = 0; i < n; i++) times that depends on the value of the argument n .
op(); The visualization below shows the value of n in each
f(n/2); of the recursive calls and the number of times op() is
f(n/2); performed at each level of the recursion tree.
} The recursion tree has lg n + 1 levels, and op() is
performed a total of n times at each level. Therefore,
the order of growth is n lg n.

f(n) n op() calls

f( n2 ) f( n2 )
n
2
+ n
2
=n op() calls
lg n + 1

f( n4 ) f( n4 ) f( n4 ) f( n4 ) 4× n
4
=n op() calls

…
n
f( nn ) f( nn ) n× n
=n op() calls

Ex.24 void f(int n) { Solution. Θ(n log n).

if (n == 0) return; This is the same as Ex.23, but the height of the tree
for (int i = 0; i < n; i++) is log 4 n instead of log2 n. The number of times op()
op(); is performed at each level is still n . Therefore, the
for (int i = 0; i < 4; i++) total is n log 4 n and the order of growth is n log n.
f(n/4);
}
 COS226 Analysis of Algorithms: Math Cheat Sheet Spring ‘20

A. Logarithms Notation:
b log n (no base) → used with
1. a = c → b = loga c Definition
orders of growth to indicate
2. logb b = 1, logb 1 = 0 Special cases
that the base is not important.
x
3. logb( ) = logb x − logb y Logarithms with different bases
y
differ by a constant factor as
4. logb(x × y) = logb x + logb y shown in the listed identities.
5. logb x y = y × logb x Follows directly from the previous rule. lg n → base 2.
logc x ln n → natural logarithm
6. logb x = Changing bases
logc b (base is e)
7. x logb y = y logb x
8. b logb x = x Follows directly from the previous rule.
9. lg(n!) = ∼ n lg n Stirling’s Approximation

B. Summations
n

∑
1. i =1+2+…+n Definition
i=1
n

∑
2. c =c +c +…+c =c ×n If c does not depend on i.
i=1
n n

∑ ∑
3. c × fi = c × fi
i=1 i=1
n n n

∑ ∑ ∑
4. fi + gi = fi + gi
i=1 i=1 i=1
n
n(n + 1)
∑
5. i =1+2+3+…+n =
i=1
2
n
n(n + 1)(2n + 1)
i 2 = 12 + 22 + 32 + … + n 2 =
∑
6.
i=1
6
n
r n+1 − 1
r i = r0 + r1 + r 2 + … + r n =
∑
7. , r ≠1 Geometric Sum.
i=0
r −1
n n
1 1 1 1 Special cases of a geometric sum
2i = 2n+1 − 1 , ( 2 )i = 1+ 2 + 4 +…+ 2 n = ∼ 2
∑ ∑
8.
(r = 2 and r = 0.5).
i=0 i=0
n n
1 1 1 1 1
∑i ∫
9. =1+ + +…+ ∼ di = ln n Harmonic Number Hn.
i=1
2 3 n 1 i

Prepared by Ibrahim Albluwi (isma@[Link]). Many thanks to Kevin Wayne for providing very valuable feedback.
Loop time complexity practice 9/6/2024

I. Time complexity of loops

Give the time complexity for the pieces of code below. Use either O or Theta (Θ) for time complexity.

The answer should be in the format covered in class.

Closed form for a summation is the answer formula for it. E.g. 1+2+3+4+…+N has closed form N(N+1)/2 .

Sample table for answers

A. Normal
0. For each of the questions below say which letters can show up in the final time
complexity. You should answer this BEFORE you solve them. E.g. i,N,k,M,t,S etc

1.
for(i=1; i<=3N; i=i+3)
for(k=1; k<=M; k=k*6)
printf("C");

2.
for(i=0; i<=(N+1); i=i+S)
for(t=1; t<=M; t=t+3)
printf("B");

3.
for(i=0; i<=N; i=i+7)

1
 for(k=1; k<=i; k=k+2)
printf("B");

4.
for(i=N; i>=1; i=i/2)
for(k=0; k<=M; k=k+S)
printf("B");

5.
for(i=N; i>=0; i=i-5)
for(k=N; k>=1; k=k/3)
printf("B");

6. Good, with function calls

// int mistery(int len, int v); has Θ(len2)
for(i=N; i>=0; i--){
int res = mistery(N, i);
for(k=N; k>=1; k=k-1)
printf("B");

7. Good.
// int mistery(int N, int v); has Θ(N2)
for(i=N; i>=0; i--){
int res = mistery(i, i);
for(k=N; k>=1; k=k-1)
printf("B");

8. Good
for (i = 101; i<=(100+N); i++)
for (k=1; k<=i; k = k+1)
printf("B ");

9. Good
for (i=1; i<=N; i=i*2)
for (k=1; k<=2*i; k=k+1)
for (t=0; t<7; t=t+1)
printf("A");

10.
for(t=1; t<=N; t=t*3)
for(i=10; i<=N; i=i+2)
for(k=N; k>=1; k=k-5)
printf("G");

2
 11.
// *** good example
for(i=1; i<=N; i=i+1)
for(k=1; k<=i; k=k+k)
for(t=1; t<=S; t++)
printf("G");

12.
for (i=1; i<=N; i=i+1) {
for (k=1; k<=i; k++) {
printf("B");
for (t=1; t<=k; t++)
printf("C");
} // end for-k
…
} // end for-i

13. good.
// Assume void do_smth(int N);has Θ(N)
for (i=1; i<=N; i=i+1) {
for (k=1; k<=i; k++) {
printf("B");
for (t=1; t<=k; t++)
do_smth(k);
} // end for-k
…
} // end for-i

14.
// example from Dr. Weems
for (i=1; i<=N-1; i++) {
…
for (k=i+1; k<=N; k++) {
temp=ab[ell][k];
ab[ell][k]=ab[i][k];
ab[i][k]=temp;
for (t=i+1; t<=N; t++)
ab[t][k] -= ab[t][i]*ab[i][k];
}// end for-k
…
} // end for-i

3
 15.
for (i=1; i<=N; i=i+i) {
for (k=1; k<=N; k++) {
printf("B");
for (t=1; t<=N; t++)
printf("C");
} // end for-k
…
} // end for-i

16. 3-level; Math manipulation required

for (i=1; i<=N; i=i*2) {
for (k=0; k<=i; k=k+3) {
printf("B");
for (t=1; t<=k; t++)
printf("C");
} end for-k
…
} // end for-i

17. Non-trivial/Hard and additional questions

for(i=N; i>=1; i--)
for(k=i; k>=1; k=k/2)
for(t=i; t<=N; t=t+2)
printf("G");
1) Write only the summation for T(N). You do NOT need to find the closed form or Theta (Θ).
2) Can you give a CLOSE lower bound and an upper bound for this time complexity? Saying that this code
takes more than lgN to run and less than N3. Is NOT CLOSE enough.

B. Non-standard loop: loop variable updates in body of loop as well.

for(i=1; i<=N; i=i+3){
printf("X");
i=i+5;
printf("Y");
}

C. i (outer) is updated based on k (inner)

Compute the time complexity (Θ) for all the code samples in this section.
1) Given the code below, assume M and N were declared and prior to execution of this code.
for(i=0, k=0; i<=N; i=i+k){
printf("%d\n", k);
for(k=0; k<M; k=k+1)
printf("G");
4
 What will this program print for M = 3 and N = 14?

True/False: if we remove k=0 from the for(k…) loop, it will not change the TC of the entire code.
True/False: if we remove k=0 from the for(i…) loop, it will not change the TC of the entire code.
2)
for(i=0, k=0; i<=N; i=i+k)
for(k=0; k<M; k=k+1)
for(t=0; t<=k; t=t+1)
printf("G");

3)
for(i=0; i<=N; i=i+k)
for(k=0; k<S; k=k+1)
printf("B");
4)
i = 0;
while (i<=N){
for(t=0, k=1; k<N; t=t+1, k=2*k)
printf("G");
i=i+t;
}

II. Generate code of certain time complexity

A. Give a piece of code with nested loops that has time complexity NlgN.

III. Exact count of loop iterations – Extra. NOT required

For each piece of code below write the function that gives the exact count of loop iterations.

A. Variations
for(k=7; k<=M; k=k+6)
printf("A");

for(k=7; k<M; k=k+6) // same as above, but k<M

printf("A");

for(i=7; i<=M; i=i*6)

printf("A");

for(i=1; i<=N; i=i+i)

printf("A");

for(i=1; i<=2N; i=i+2)

printf("A");
5

Powered by TCPDF ([Link])

 Master Theorem:
Practice Problems and Solutions

Master Theorem
The Master Theorem applies to recurrences of the following form:

T (n) = aT (n/b) + f (n)

where a ≥ 1 and b > 1 are constants and f (n) is an asymptotically positive function.
There are 3 cases:

1. If f (n) = O(nlogb a− ) for some constant  > 0, then T (n) = Θ(nlogb a ).
2. If f (n) = Θ(nlogb a logk n) with1 k ≥ 0, then T (n) = Θ(nlogb a logk+1 n).
3. If f (n) = Ω(nlogb a+ ) with  > 0, and f (n) satisfies the regularity condition, then T (n) = Θ(f (n)).
Regularity condition: af (n/b) ≤ cf (n) for some constant c < 1 and all sufficiently large n.

Practice Problems
For each of the following recurrences, give an expression for the runtime T (n) if the recurrence can be
solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply.

1. T (n) = 3T (n/2) + n2

2. T (n) = 4T (n/2) + n2

3. T (n) = T (n/2) + 2n

4. T (n) = 2n T (n/2) + nn

5. T (n) = 16T (n/4) + n

6. T (n) = 2T (n/2) + n log n

1 most of the time, k = 0

1
 7. T (n) = 2T (n/2) + n/ log n

8. T (n) = 2T (n/4) + n0.51

9. T (n) = 0.5T (n/2) + 1/n

10. T (n) = 16T (n/4) + n!

√
11. T (n) = 2T (n/2) + log n

12. T (n) = 3T (n/2) + n

√
13. T (n) = 3T (n/3) + n

14. T (n) = 4T (n/2) + cn

15. T (n) = 3T (n/4) + n log n

16. T (n) = 3T (n/3) + n/2

17. T (n) = 6T (n/3) + n2 log n

18. T (n) = 4T (n/2) + n/ log n

19. T (n) = 64T (n/8) − n2 log n

20. T (n) = 7T (n/3) + n2

21. T (n) = 4T (n/2) + log n

22. T (n) = T (n/2) + n(2 − cos n)

2
Solutions
1. T (n) = 3T (n/2) + n2 =⇒ T (n) = Θ(n2 ) (Case 3)

2. T (n) = 4T (n/2) + n2 =⇒ T (n) = Θ(n2 log n) (Case 2)

3. T (n) = T (n/2) + 2n =⇒ Θ(2n ) (Case 3)

4. T (n) = 2n T (n/2) + nn =⇒ Does not apply (a is not constant)

5. T (n) = 16T (n/4) + n =⇒ T (n) = Θ(n2 ) (Case 1)

6. T (n) = 2T (n/2) + n log n =⇒ T (n) = n log2 n (Case 2)

7. T (n) = 2T (n/2) + n/ log n =⇒ Does not apply (non-polynomial difference between f (n) and nlogb a )

8. T (n) = 2T (n/4) + n0.51 =⇒ T (n) = Θ(n0.51 ) (Case 3)

9. T (n) = 0.5T (n/2) + 1/n =⇒ Does not apply (a < 1)

10. T (n) = 16T (n/4) + n! =⇒ T (n) = Θ(n!) (Case 3)

√ √
11. T (n) = 2T (n/2) + log n =⇒ T (n) = Θ( n) (Case 1)

12. T (n) = 3T (n/2) + n =⇒ T (n) = Θ(nlg 3 ) (Case 1)

√
13. T (n) = 3T (n/3) + n =⇒ T (n) = Θ(n) (Case 1)

14. T (n) = 4T (n/2) + cn =⇒ T (n) = Θ(n2 ) (Case 1)

15. T (n) = 3T (n/4) + n log n =⇒ T (n) = Θ(n log n) (Case 3)

16. T (n) = 3T (n/3) + n/2 =⇒ T (n) = Θ(n log n) (Case 2)

17. T (n) = 6T (n/3) + n2 log n =⇒ T (n) = Θ(n2 log n) (Case 3)

18. T (n) = 4T (n/2) + n/ log n =⇒ T (n) = Θ(n2 ) (Case 1)

19. T (n) = 64T (n/8) − n2 log n =⇒ Does not apply (f (n) is not positive)

20. T (n) = 7T (n/3) + n2 =⇒ T (n) = Θ(n2 ) (Case 3)

21. T (n) = 4T (n/2) + log n =⇒ T (n) = Θ(n2 ) (Case 1)

22. T (n) = T (n/2) + n(2 − cos n) =⇒ Does not apply. We are in Case 3, but the regularity condition is
violated. (Consider n = 2πk, where k is odd and arbitrarily large. For any such choice of n, you can
show that c ≥ 3/2, thereby violating the regularity condition.)

3
Practice Question