CSC 320: Summer 2017
Tutorial #2, Tues. May 16, 1:30pm or 2:30pm
Learning Objectives:
The goals of this tutorial are:

A review of Big Oh notation. This material is
critical for success in CSC 320 and should have
been learned in CSC 225.

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, ..., n1.
The graph H= Gv is the same as the graph G except that
vertex v and all edges incident to v are deleted.

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

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)?

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)?

The definition of Big Oh is that for functions f and g
which map the natural numbers to nonnegative real values, the function
f(n) is in O(g(n)) if there exists constants c > 0
and n_{0} >= 0
such that for all n >= n_{0}, f(n) <= c * g(n).
Use this definition to prove that the polynomial
a_{0} x^{0}
+ a_{1} x^{1}
+ a_{2} x^{2}
...
+ a_{k} x^{k}
is in O(x^{ k}),
when a_{i} >= 0 for all i= 0, 1, 2, ..., k.
Part 2: Other questions

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