if T(dec_path) = f(|input|) (see page 244 for how the representation affects the time)
then T(opt_path) = (|V|-1) * f(|input|)

|input| = adjacency matrix (list) + space to store costs

G = (V,E) , | V | = n, | E | = m

c = max cost of any edge

|input| = n² + mlog c    bits

T (dec-path) = f (n² + mlog c)

T (opt-path) = (n-1) * c * f(n² + mlog c)

T (opt-path) not within a polynomial factor of T(dec-path).

Exercise: can you write opt-path in terms of dec-path such that T(opt-path) < p (|input|) * T (dec-path)?

Input in binary

|input| = n² log₂ w (w = max. cost)

T (dec-path) = f (n² log₂ w)

T (opt-path) = (n-1) * w * f (n² log₂w)

T (opt-path) not within polynomial factor of T (dec-path)

Input in unary

|input| = n² w

T (dec-path) = f (n² w) ;

T (opt-path) = (n-1) * w * f (n² w)

T (opt-path) within polynomial factor of T (dec-path)

T (opt) = polynomial (|input|) * T(dec)