Conflicting definitions of quasipolynomial time

Question

The textbook The Nature of Computation uses the following definition of quasipolynomial time:

A quasipolynomial is a function of the form $f(n) = 2^{\Theta(\log^k n)}$ for some constant $k > 0$, where $\log^k n$ denotes $(\log n)^k$. Let us define QuasiP as the class of problems that can be solved in quasipolynomial time.

So presumably the definition for QuasiP could be written $TIME(\bigcup_k 2^{\Theta(\log^k n)})$. However every other definition I've found on the web, in particular the one from Wikipedia, suggests the alternative definition $TIME(\bigcup_k 2^{O(\log^k n)})$.
Now I can't see how these definitions are supposed to be equivalent. In fact I can imagine that there's a function $f$ that requires $2^{\log n}$ steps for even values of $n$ and $1$ step for odd values of $n.$ $f$ would fail to be in $2^{\Theta(\log^0 n)}$ because of the even values of $n$ and it would fail to be in $2^{\Theta(\log^k n)}$ for any $k > 0$ because of the odd values of $n$. However $f$ is still in $2^{O(\log^1 n)}$.
So apparently such an $f$ is in QuasiP according to the second definition but not according to the first. Did I make a mistake in the reasoning here? And if not am I correct in assuming that the definition in The Nature of Computation is erroneous?

Answer 1

The equality

$Time\left(\bigcup\limits_k 2^{O\left(\log^k n\right)}\right)= Time\left(\bigcup\limits_k 2^{\theta\left(\log^k n\right)}\right)$

is an equality betweeen two sets of languages decidable by certain Turing machines, and not an equality between sets of functions $f:\mathbb{N}\rightarrow\mathbb{N}$.

The function you constructed is an example of a function in $\bigcup\limits_k 2^{O\left(\log^k n\right)}\setminus \bigcup\limits_k 2^{\theta\left(\log^k n\right)}$, but this does not contradict the above equality.

Let $L\in Time\left(2^{O\left(\log^k n\right)}\right)$ for some $k\in\mathbb{N}$, be a language decidable by a Turing machine which runs in time $2^{O\left(\log^k n\right)}$. You can simply construct an equivalent Turing machine which runs in time $2^{\theta\left(\log^k n\right)}$ by adding redundant steps in case the computation ended too quickly, and this shows $L\in Time\left(2^{\theta\left(\log^k n\right)}\right)$.

Answer 2

Both definitions are equivalent, since when we say that a problem can be solved in time $t$, we usually mean that it can be solved in time at most $t$. For example, a problem can be solved in time $n$ if there is an algorithm solving it whose running time $T(n)$ satisfies $T(n) \leq n$.