c++ - 如何计算函数的搜索复杂度

Question

我有以下两个功能，我正在尝试比较时间复杂度
我的第一个功能是一个简单的for循环:

For (i=0;i<m;i++)
// do stuff

时间复杂度:

i=0 is executed once

i< n is executed n+1 times

i++ is executed n times

= 2n+2 = 0(N)

我正在努力为第二个功能计算我的时间复杂度:

void search(string word)
{
    Index index;
    if (tree.AVL_Retrieve(word, index)) {
        for (auto i : index.idList)
        {
            
             for (int j=0;j<m;j++)              
                 {
                    //do stuff
                  }
        }   
    }
}

我相信AVL树中的检索是O(logN)，我的循环是O(N)，然后我的内部循环是O(M)，但总体而言，我将如何编写该搜索函数的时间复杂度。
注意:我们可以假设我的AVL树中有N个键

Answer 1

第一个for循环运行(m-1)时间，因此具有时间复杂度O(m)。

第二个函数一次运行AVL_Retrieve函数，并为index.idList的每个循环计数运行一次，从而给出了O(log (number of nodes in tree))+O((count of index.idList)*m)的复杂性