Given two inputs $x$ and $y$ where $x$ is of arbitrary size and $y$ is variable with respect to $x$, $y$ is transformed into a square table $T$ and $x$ into its row headings $h$ according to a rule. Then $x$ and $y$ are discarded. This takes O($x^2$) time and is not in question.
Alternatively, $T$ and $h$ may be generated first and then transformed into $x$ and $y$ to verify results later.
An algorithm searching for patterns in $T$ takes several rows from $T$ and calculates with them, returning values interpreted in terms of $h$ to determine the next rows to be used. Each calculation will be a boolean AND, OR, XOR, or NOT, and so takes $(r – 1)\sqrt{T}$ operations, where $r$ is the nubmer of rows involved in the calculation. In the worst case for any one calculation, all rows in $T$ may be returned, but this means the algorithm will exit on the next calculation. In the worst case overall, each row in $T$ is guaranteed to be used at least O($T$) times.
The algorithm is structured such that there are a finite number of calculations inside a finite loop inside another finite loop. The question is what to consider “the input” for the purposes of calculating time complexity of this algorithm.
In terms of $T$ the algorithm performs in the worst case O($T$) operations inside O($\sqrt{T}$) loops inside O($T$) loops and then exits. The time complexity for this would be O($T \times \sqrt{T} \times T$) or O($T^2 \sqrt{T}$).
If $t$ is a row in $T$, then in terms of $t$ the algorithm performs in the worst case O($t^2$) operations inside O($t$) loops inside O($t^2$) loops and then exits. The time complexity for this woiuld be O($t^2 \times t \times t^2$) or O($t^5$).
I have assumed while writing the algorithm that, since I was focused on calculating with rows, I should state the complexity in terms of $\sqrt{T}$, or $t$, the size of the inputs to each individual calculation. However, other people point out that $t$ is only part of the input to the whole second algorithm, so the time complexity should be stated in terms of the whole input $T$ (if not $T + h$), and while I’m starting to come around to that point of view, I’m not entirely sold on it yet.
Should the time complexity be stated in terms of $T$ or $t$?
Also, if $T$ is the correct basis for stating the time complexity, should the “$\sqrt{T}$” be dropped and the time complexity stated as just O($T^2$)?
Best Answer
Mathematically speaking, the answers in terms of $t$ and $T$ are exactly the same, and the choice of which variable to use has no significance; they're equally correct answers.
Conventionally speaking, runtime is usually expressed in terms of the size of the whole input when possible, so runtime for a function that takes in a row would be expressed in $t$ and runtime for a function that takes in the whole table would be expressed in the size of the table $T$. It's not a definite rule, though: many algorithms on tables are expressed in terms of the column and row sizes, many algorithms on trees are expressed in terms of the height of the tree and the branching factor, and so on.
It's only valid to drop bounded functions (functions that are smaller than some constant) in $O$-notation. So it's not possible to drop $\sqrt{T}$; $O(T^2)$ and $O(T^2\sqrt{T})$ are different.