CODEWITHSUNDEEP
c++big-o
william_
william_

Reputation: 1133

how to work out the search complexity of a function

I have the following two functions and i am trying to compare the time complexity my first function is a simple for loop:

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

Time complexity:

i=0 is executed once

i< n is executed n+1 times

i++ is executed n times

= 2n+2 = 0(N)

i am struggling to work out my time complexity for this second function:

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
                  }
        }   
    }
}

i believe that retrieve in AVL tree is O(logN) and my loop is O(N) and then my inner loop is O(M), but as a whole how would i write the time complexity for that search function.

note: we can assume there are N keys in my AVL tree

Upvotes: 2

Views: 53

Answers (1)

kesarling
kesarling

Reputation: 2238

The first for loop runs for (m-1) times, thus having time complexity O(m).

The second function runs the AVL_Retrieve function once and for each loop count of index.idList times, giving the complexity O(log (number of nodes in tree))+O((count of index.idList)*m)

Upvotes: 1

Related Questions