受数据值影响的Big O时间复杂度：给定伪代码的复杂度求解

咱们一步步拆解这个伪代码的时间复杂度，搞清楚它的Big O量级：

• 外层循环的执行次数：
  外层循环从i=1跑到arraySize（也就是数组长度n），总共会执行n次迭代——不管数组里存的是什么，只要长度是n，这部分的次数就固定和n成正比。

• 内层循环的执行次数：
  内层循环每次会跑firstValue次，这个firstValue是数组第一个元素，题目说它是≥1的无界正数，但关键是：它的大小和数组长度n没有任何关系，是一个独立于n的输入值。不管它是1还是100万，对于n的增长来说，它都是个固定的常数。

• 总运行时间计算：
  内层循环里的操作是常数时间（O(1)），所以总操作次数就是外层循环次数 × 内层循环次数 × 常数操作时间，也就是n × C × O(1)（这里C代表firstValue的大小）。在Big O表示法里，常数因子会被忽略，所以最终的复杂度就是O(n)。

简单说，当数组长度n增长时，运行时间会跟着线性增长，和第一个元素的大小无关——哪怕第一个元素特别大，也只是给整个运行时间乘了个固定的系数，不会改变增长趋势。

所以g(n) = n，算法的时间复杂度是O(n)。

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