# Learning Objectives:

The goals of this tutorial are:

1. A review of Big Oh notation. This material is critical for success in CSC 320 and should have been learned in CSC 225.
2. Please also bring any other questions you have about the course material.

# Tutorial Part 1: Time Complexity

For the following questions, assume that G is an undirected graph having n vertices. The vertices of G are numbered 0, 1, 2, ..., n-1. The graph H= G-v is the same as the graph G except that vertex v and all edges incident to v are deleted.

1. Give the time complexity using Big Oh notation of this code segment:
```for (i= 0; i < n; i++)
{
for (j=i+1; j < n; j++)
{
for (k= j+1; k < n; k++)
{
Take an adjacency matrix for G and make
an adjacency matrix for H= G -i -j -k
(i, j, and k are vertices of G).
}
}
}
```
2. Consider:
```for (i= 0; i < n; i++)
{
for (j=i+1; j < n; j++)
{
for (k= j+1; k < n; k++)
{
Call a function compute_parameter(G) which has
time complexity O(f(n)) where n is the number of
vertices of G.
}
}
}
```

(a) Express the time complexity of this code in terms of f(n).
(b) What is the time complexity when f(n) is O(1)?
(c) What is the time complexity when f(n) is O(n^3)?
(d) What is the time complexity when f(n) is O(2^n)?

3. ```for (i= 0; i < n; i++)
{
for (j=i+1; j < n; j++)
{
for (k= j+1; k < n; k++)
{
Take an adjacency matrix for G and make
an adjacency matrix for H= G -i -j -k
(i, j, and k are vertices of G).
Call compute_parameter(H)
}
}
}
```
What is the time complexity of this code assuming that the time for compute_parameter is in O(f(n)) for some function f(n)?

4. The definition of Big Oh is that for functions f and g which map the natural numbers to non-negative real values, the function f(n) is in O(g(n)) if there exists constants c > 0 and n0 >= 0 such that for all n >= n0, f(n) <= c * g(n). Use this definition to prove that the polynomial a0 x0 + a1 x1 + a2 x2 ... + ak xk is in O(x k), when ai >= 0 for all i= 0, 1, 2, ..., k.

# Part 2: Other questions

1. Prove that the set S= { L : L is a language over {0,1}*} is not countable.