For each of the following find the order of the given function.
f(x) = x2 + 2x
f(x) = 17 + 24 × 5
f(n) = 37n! + 2n
f(x) = 4,982,734 + 49,827,420x + 3458291x2 + ½x3
f(n) = (1 + n)log n
f(n) = log [n(1 + n)]
Show that for any positive functions f, g and h,
if f(x) ∈ O(h(x)) and
g(x) ∈ O(h(x)) then the function
(af(x) + bg(x)) ∈ O(h(x))
for every real number a and b.
(Hint: Use the limit definition of O, quote any properties
of limits you use.)
For this question let A =
v1
v2
v3
v4
v5
0
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
0
1
1
0
1
1
0
Given the adjacency matrix A above, draw the corresponding graph G.
Write down the corresponding adjcency list for G.
Write down the corresponding adjcency table for G.
Use the adjacency matrix method to find the number of paths of length 3 from
v1 to v2.
Identify these paths on your picture.
Since there is no edge between v1 and v2W0(v1, v2) = ∞.
Without calculating them explain why W1(v1,
v2) = W2(v1, v2) = ∞
Find Wk(v1, v2) for
k = 3, 4 and 5.
Draw the shortest path(s) from v1 to v2,
how many are there?
Given a graph with 1,000 vertices, if we use the "W" method to find
the length of shortest path between to given points, roughly how many steps
would you expect to use?
Can you think of an algorithm based on matrix multiplication to find the
shortest path between two given points?
Given that matrix multiplication is roughly O(n2)
what is the complexity of your algorithm?
