小循环的Big-O

Question

我在为Uni做的练习中遇到问题，如下所示：

此函数接收字符串s，如果s包含给定字符串sub的两个首字母（小写和任意订购）。否则，它返回false。

一些示例：假设sub =“ Euler”，然后检查'e'和你'。从而，s =“愿力量与你同在”，然后返回true。s =“房间31”，然后返回false。s =“ un93ike1s”，然后返回true。

选择以下最严格的（最坏情况下的时间）复杂度行。

function contains_two_letters(s, sub, n)

/* create a vector with two entries, both set to false */ 
found = [ false, false ]               (1)

for (i = 0; i < n; i++)                (2)
    for (k = 0; k < 2; k++)            (3)
        if s[i] == sub[k]:             (4)
            found[k] = true
            break
return (found[0] and found[1])

我知道/假设：（（1）是O（1），

（（2）是O（n）和

（（4）是O（1），

但是（3）呢？

问题：我们从未见过仅运行两次的循环示例，因此我假设它是O（2），但在下拉列表中不是一个选项。

可用选项为O（n），O（1），O（n ^ 2）和O（log（n））

任何帮助将不胜感激。

Answer 1

[记住，Big-O并不直接与算法的性能或操作数量有关：而是与随着问题规模的增加而跟踪操作数量changes

的方式有关。