算法渐近复杂度

我想知道这个过程可以使用大θ符号在以下算法中返回的最小值和最大值是多少。算法是：

procedure F(????[1..n])
   s = 0
   for i = 1 to n
      j = min(max(i,A[i]),n³) 
      s = s + j
   return s

编辑：删除了原始答案，因为它是针对错误的问题。

分析取决于以下几行：

min(max(i,A[i]),n³) 

如果我们弄清楚了这种情况，那么我们就可以轻松地找出结果的情况。我们必须回答是否i > A[i]然后是否较大者i and A[i]大于n^3.

1. i > A[i] and i > n^3。事实并非如此，因为i <= n and i, n是整数。
2. i > A[i] and i < n^3。如果，例如，A[i] = -1。在这种情况下，我们添加i一起为了0 <= i <= n。结果是n(n+1)/2，即O(n^2)。 （我在用O但 Theta 也适用）。
3. i < A[i] and A[i] < n^3。如果发生这种情况，i + 1<= A[i] <= n^3 - 1 and n > 2。在这种情况下，我们添加i + 1一起n次，对于i equal 1 to n，或者我们添加n^3 - 1一起n次。在低端我们得到n(n-1)/2 - n，和之前一样-n术语为-1，在高端我们得到n^4 - n;介于两者之间O(n^2) and O(n^4).
4. i < A[i] and A[i] > n^3。如果发生这种情况，A[i] > n^3。在这种情况下我们有n^3 summed n次n^4, O(n^4).

基于上述，我的想法是最好情况的下限是Omega(n^2)最坏情况的上限是O(n^4)。这两个界限对于各自的情况都是严格的，但由于它们不同，我们不能给出结果增长率的单一严格界限。