Computational complexity of truncation

Question

Let $A$ be an $m \times n$ matrix, $\mathbf x \in \mathbb R^n$, and define the truncation operator $T \colon \mathbb R^m \to \mathbb R^m$ by $(T \mathbf y)_i = \max\{\min\{\mathbf y_i, c\}, 0\}$, so $T$ truncates each entry of its argument to $[0, c]$.

What is the computational complexity of $TA\mathbf y$?

I know from Wikipedia that $A \mathbf y$ should be $O(mn)$. What about $T$? I might be totally wrong, but if $T$ has to make 2 comparisons over each of $m$ elements, would it be $O(m)$? So the total complexity of $TA\mathbf y$ would be $O(m^2n)$?

Is this right? Thanks.

Answer 1

Updated answer:

No. Given that the truncation operator :$ℝ^→ℝ^$ by $()=max\{min\{,\},0\}$, it's reasonable to deduce that it takes $O(m)$.

Matrix multiplication takes $O(m n)$, and then we get a new vector Ay, applying T on it takes another O(m).

Hence, it takes O(mn+m) = O(mn) in total.

(Exception is that it's done in designated hardware, where it could be parallelized, as low as O(1) for truncation operator.)

Answer 2

No, that's not correct. It takes $O(mn)$ time to compute $Ay$. Then, it takes $O(m)$ time to apply $T$ to that result. So, the total running time is $O(mn+m)$. Equivalently, the total running time is $O(mn)$.

In my experience, the $T$ operation is normally known as clipping, not truncation.