（$2.5$ 分）若输入的 $d[i]$ 为 $i$，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。

{{ select(1) }}

• $O(n), O(n^2)$
• $O(n),O(n \log n)$
• $O(n \log n),O(n^2)$
• $O(n \log n),O(n \log n)$