# Name for algorithms whose runtime only depends on the problem size?

I'm looking for the name of the family of algorithms whose exact runtime is dependent only on the size of the input. An example of such an algorithm would be naive $$O(n^3)$$ matrix multiplication. If we know $$n$$, we know exactly how many operations it will execute and how many cycles it will take to complete (ignore real world things like cache misses, context switching, etc.). An algorithm that would not be in that family is Quick sort ($$O(n^2)$$) since the number of operations is dependent on the contents of the list being sorted. Divider algorithms that only depend on the number of bits of the operands would be in this family, but Euclid's algorithm would not because it finishes faster for some numbers than others.

In other words, suppose you have the algorithm implemented in assembler and the cpu runs one instruction per cycle. Then the value of the program counter $$pc(t, n)$$ is a function of time $$t$$ and problem size $$n$$. The total number of cycles to compute the solution is known in advance.

• I guess oblivious algorithms form an important subclass of things you are interested in (see Computational Complexity: A ModernApproach , remark 1.10 p1.11 (21) Oct 12, 2022 at 21:16
• Oblivious may be the word I'm looking for. Though most google hits for "oblivious algorithms" are for "cache-oblivious algorithms" which is something different. Oct 12, 2022 at 23:43
• Though most google hits for "oblivious algorithms" are for "cache-oblivious algorithms" I know:) Not that you mention it, I'm not actually sure if "oblivious algorithms" is a standard name. I'm only sure that "oblivious TM" is a standard name: en.wikipedia.org/wiki/… Oct 13, 2022 at 0:14
• Are you talking about Big O vs Big Theta?
– Neil
Oct 13, 2022 at 5:50
• The family I'm thinking of is a subset of $\Theta$-bound algorithms. Tell me the size of the matrices, bits of the operands or whatever, and I tell you the exact number of RAM operations required. Oct 13, 2022 at 13:58

• Don't know about others, but if someone tells me that $A$ is a "constant-time algorithm", I will 100% understand it as $A$ having $O(1)$ running time. Wikipedia seems to agree: en.wikipedia.org/wiki/Time_complexity#Constant_time Oct 12, 2022 at 21:21