1
$\begingroup$

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$.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.