30 marks in total

Problem 1
---------

[Marking scheme: three marks for correct, one mark for slightly wrong e.g. saying "check if every node in S is in G."]

Check if every node in G is in S.

Problem 2
---------

[Marking scheme: Each part is marked out of 2. One mark for getting what's on the left of the "=" correct and one mark for getting what's on the right of the "=" correct. Except for the last one, which is worth 1 mark in total. If they have a +1 or -1 incorrect, ignore it.]

1 x 3 = O(1)
m x (0.5m(m-1))((2m+1)+(2m+1)) = O(m^{4})
m x (m+2) = O(m^{2})
1 x m^{2} = O(m^{2})
O(m^{4})

Problem 3
---------

[Marking scheme: same as above.]

1 x 2 = O(1)
1 x (m - 1)(2m(m - 1)) = O(m^{3})
1 x 1 = O(1)
O(m^{3})

Problem 4
---------

[Marking scheme: same as above.]

1 x m^{2} = O(m^{2})
1 x m^{2} = O(m^{2})
1 x 2 = O(1)
1 x (m - 1)(2m(m - 1)) = O(m^{3})
1 x 1 = O(1)
O(m^{3})