Find the upper bound of computing time

Question

Please explain how to solve this??

What is the upper bound of computing time of m coloring decison problem for n nodes?

a. O( n ^m)

b. O( m ⁿ)

c. O( n m ⁿ )

d. O( m n ^m )

e. O( n ^m m ⁿ )

Comments

I do not think we can have an upper bound of computing time for PROBLEMS. Event to do 1+1, I can do 

while(1){} return 1+1;

which will take infinite time. 

---

Key says answer is O( n m ⁿ )

I wonder how to solve this?!

Answer 1

Generally the solution of m-coloring on n vertex graph can be represented as an array c[1..n], where c[i] represents color of vertex i. A brute-force method will generate $m^n$  assignments. Verifying these $m^n$ options on n vertices in worst case will take n$m^n$ time. So, $O(nm^n) $ will be the upper bound.