向固定大小为3的数组插入元素是否为常数时间？整体算法时间复杂度是否为O(n)？

插入操作的时间复杂度判断 #

你的结论正确，这个插入+切片的操作确实是常数时间O(1)。
你维护的res数组大小被严格限制为最多3个元素：每次执行append后数组长度最多为4，随后的res[:3]切片操作最多只需要复制3个元素生成新数组。Python中列表切片的时间复杂度和切片长度成正比，这里切片长度固定不超过3，和输入数组的长度n完全无关，不管输入规模多大，这一步的耗时永远固定，属于标准的常数时间操作。

整体算法的时间复杂度判断 #

如果每次迭代中除了上述插入操作外，其余计算逻辑也都是常数时间（没有随输入规模n增长的遍历、递归等操作），那么整体算法的时间复杂度确实是O(n)。
总耗时为n次迭代的耗时之和，单次迭代耗时为固定常数，最终整体复杂度就是线性的O(n)。

内容的提问来源于stack exchange，提问作者Patrick_Chong