一个伪代码，说明它的最好最坏性能

Question

求它最好情况（下界）？
最坏情况（上界）？
紧界（如果有的话）？

Answer 1

AlgorithmEx1 ((ar, ..., an)):
    x <- 0                      // 1
    for i <- 1 to n - 1 do      // * (n - 1)
        if ai > an              // cond is 0 or 1
            x <- x + ai         // 1
    return x

t(n) = T(1 + (n - 1) * (cond + 1))
     = T(n * (cond + 1) - (cond + 1) + 1)

t(n) =
{
    T(n)    // cond = 0    // 最好情况
    T(2n)   // cond = 1   // 最坏情况
    T(1.5n) // (a1, ... an) 是均匀分布 平均情况