They allocate a target blob of the required size and then copy the values, so it is proportional to the total size. In degenerate cases (0-sized tensors) you would also have things that perform with the number of operands, for non-degenerate cases this is bounded by the total size.
Strictly speaking, the number of dimensions also plays a role, but in terms of asymptotic analysis you would soon discover that there is a hard upper bound for the number of dimensions you can use with PyTorch anyway.
The most common pitfall to avoid is to grow tensors by using growing_list = cat(growing_list, new_item) in a loop because that will give quadratic complexity (in the iteration size from having effort proportional to i in the i-th loop), which becomes noticeable quite fast.
Best regards
Thomas