У меня есть задание, которое хочет, чтобы я написал троичный алгоритм поиска и впоследствии вычислил его временную сложность. Я смог написать алгоритм для него, но не смог придумать идеи, как вычислить его сложность. Я думаю, что я не понял концепцию бета-тета-записи.

Вот мой код: он работает как бинарный поиск, но только делит список на части и продолжает поиск таким образом.

    *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";

Если бы вы могли объяснить, как определить его сложность в терминах бета-тета-нотации, это было бы очень полезно для меня.