The upper bound of computing time of m coloring decision problem, i.e. the…
2012
The upper bound of computing time of m coloring decision problem, i.e. the tightest worst-case time bound among the options given, is
Answer: C. O(nmn) — Concept: The running time of a backtracking algorithm equals the number of nodes it generates in the state-space tree multiplied by the work it performs at…
- A.
O(nm)
- B.
O(nm)
- C.
O(nmn)
- D.
O(nmmn)
Attempted by 6 students.
Show answer & explanation
Correct answer: C
Concept: The running time of a backtracking algorithm equals the number of nodes it generates in the state-space tree multiplied by the work it performs at each node. When a problem is solved by taking n successive decisions and every decision offers m candidate values, the tree has one level per decision and m branches per level, so it contains 1 + m + m2 + ... + mn nodes, a count of order mn.
Application to the m-colouring decision problem:
The m-colouring decision problem asks whether the n vertices of a graph can be coloured with at most m colours so that no edge joins two vertices of the same colour. The state-space tree colours one vertex per level and offers m candidate colours at each level.
The number of internal nodes of this state-space tree is 1 + m + m2 + ... + mn-1 = (mn - 1)/(m - 1).
At an internal node the NextValue routine tries the m candidate colours and, for each one, scans the adjacency row of the current vertex across all n vertices, so the work per internal node is O(mn).
Total time = O(mn) × (mn - 1)/(m - 1) = O(nmn+1/(m - 1)) = O(nmn).
Cross-check: the geometric sum is dominated by its largest term, since for every m of at least 2 the value (mn - 1)/(m - 1) lies between mn-1 and 2 mn-1. The node count is therefore of order mn-1 and the factor m/(m - 1) contributes only a constant. Multiplying that node count by the O(mn) work per internal node again gives O(mn) × mn-1 = O(nmn), so this second route reaches the same upper bound as the step above, which is the order standardly quoted for this algorithm.
Contrast with the other expressions:
O(nm) is the amount of work performed at one node of the state-space tree; it does not account for how many nodes the tree contains.
O(nm) interchanges the roles of n and m: it counts m decisions with n candidate values each, not n decisions with m candidate values each.
O(nmmn) is a valid but far looser bound: it multiplies two exponential terms and is much larger than the O(mn) × (mn - 1)/(m - 1) work the algorithm performs, so it is not the tightest bound among the options given.