In the theta notation definition, is it possible that $n_0$ could equal 0?

This is the definition of theta notation:

The function $$T(N)$$ is $$\Theta(g(N))$$ if there exist positive constants $$C_1$$, $$C_2$$ and $$N_0$$ such that $$C_1g(N) \le T(N) \le C_2g(N)$$ for all $$N \ge N_0$$.

My calculation is below. When I solved the inequality, $$N \ge 0$$. Am I making a mistake or am I on the right track?

Assuming 1 time unit equals 1 memory read or write, I have counted the time units to get to the expression $$T(N) = 4KN + 37N + 11K + 22$$.

This is a sorting algorithm that uses hashing. The inputs are an array $$A$$ of non-negative integers of length $$N$$, $$k$$ is the largest integer value in $$A$$, and $$a$$ and $$b$$ are positive integers. I also implemented this in javascript and the output is wrong so I think whoever made this made a mistake.

function Sort(A,N,k,a,b)
C=new array(N) of zeroes    // 4 time units
R=new array(N) of zeroes   // 4 time units
pos=0 // 3
for 0 <= j < N          // 7N+5 time units
C[(a*A[j]+b)%N]=C[(a*A[j]+b)%N]+1 // 20N time units
for 0 <= i < N          // 7N+5 time units
for pos <= r < pos+C[(a*i+b)%N] // 11K time units
R[r]=i     // 4KN time units
pos=r =       // 3N time units
return R         // 1 time unit
end function


The function $$T(N)$$ is $$\Theta(g(N))$$ if there exist positive constants $$C_1$$, $$C_2$$ and $$N_0$$ such that $$C_1g(N) \le T(N) \le C_2g(N)$$ for all $$N \ge N_0$$.

We can prove that $$T(N) = 4KN + 37N + 11K + 22 = \Theta(g(KN))$$.

$$(T(N) = 4KN + 37N + 11K + 22) \le (g(N) =4KN + 37N + 11K + 22 + KN)$$

$$(T(N) = 4KN + 37N + 11K + 22) \le (g(N) = 5KN + 37N + 11K + 22)$$

Therefore, the value of $$C_2$$ becomes 5. If we solve the above inequality for $$N$$, $$N \ge 0$$.

• Answer to title: yes, why not? Look at $f(n)\in\Theta(f(n))$. Mar 17, 2022 at 1:01

It doesn't matter whether you allow $$N_0 = 0$$ or not (though per your definition, it is not allowed). If $$C_1 g(N) \le T(N) \le C_2 g(N)$$ holds for all $$N \ge 0$$, then in particular, it holds for all $$N \geq 1$$, or for all $$N \geq 1000$$, for that matter.
The condition "$$C_1 g(N) \le T(N) \le C_2 g(N)$$ for all $$N \ge N_0$$" only requires that if $$N \ge N_0$$ then $$C_1 g(N) \le T(N) \le C_2 g(N)$$. There is not requirement in the other direction. It's not an if-and-only-if.