Search code examples
searchtimecomplexity-theory

Time Complexity of Ternary Search Algorithm

I have an assignment that wants me to write an ternary search algorithm and compute its time complexity afterwards. I was able to write an algorithm for it but I couldn't come up with any ideas how to compute its complexity. I think I didn't understand the concept of big-theta notation.

Here is my code: It works like binary search but only divides the list into there pieces and continues the search like that.

    *some list which contains n increasingly-ordered integers;*

    int num;

    int min = 1;
    int max = n;

    int middle1 = (2*min+max)/3; 
    int middle2 = (min+2*max)/3;

    cin >> num;    //num is the number that is wanted to be found

    while (middle1 != middle2)
    {
        middle1 = (2*min+max)/3;
        middle2 = (min+2*max)/3;

        if(num <= list[middle1])
            max = middle1;
        else if(num >list[middle1] && num <= list[middle2])
            {
                    min= middle1; 
                    max = middle2;
            }
        else
            min = middle2;
    }
    if(num == list[max])
        cout << "your number is found in the "<< max <<"th location\n";
    else
        cout << "number cannot be found";

If you could explain how to determine its complexity in terms of big-theta notation, it would be very helpful for me.

Solution

  • At each step, you are reducing the size of the searchable range by a constant factor (in this case 3). If you find your element after n steps, then the searchable range has size N = 3n. Inversely, the number of steps that you need until you find the element is the logarithm of the size of the collection. That is, the runtime is O(log N). A little further thought shows that you can also always construct situations where you need all those steps, so the worst-case runtime is actually Θ(log N).