Временная сложность алгоритма

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
 
 
//алгоритм Евклида
int gcd (int a, int b)
{
    while (b != 0)
    {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
} //O(N)
 
//заполняем массив рекурсивной процедурой
void fill(const int left, const int right, const int pos, const std::vector<int> &a, std::vector<int> &gcd)
{
    //если приходим в отрезок длины 1, значит записываем в gcd значение массива a
    if (left == right)
    {
        gcd[pos] = a[left];
    }
    //иначе в случае нечетного размера отрезкa, мы его поделим, даже пусть это будут не равные части; 
    //а в случае четного размера, нужно получить равные части.
    else
    {
        int leftEnd = (left + right) >> 1;
        int rightBegin = leftEnd + 1;
        fill(left, leftEnd, (pos << 1) + 1, a, gcd);
        fill(rightBegin, right, (pos << 1) + 2, a, gcd);
        gcd[pos] = ::gcd(gcd[(pos << 1) + 1], gcd[(pos << 1) + 2]); //заполняем gcd
    }
} //O(logN)
 
//поиск
int getGcd(int qLeft, int qRight, const int left, const int right, const int pos, const std::vector<int> &gcd)
{
    //если мы не попали в интервал, то возвращаем 0
    if (qRight < left || right < qLeft)
    {
        return 0;
    }
    //обновляем left, right
    qLeft = std::max(qLeft, left);
    qRight = std::min(qRight, right);
    //если отрезки совпали, то возвращаем gcd[pos]
    if (qLeft == left && qRight == right)
    {
        return gcd[pos];
    }
    assert(left < right);
    int leftEnd = (left + right) >> 1;
    int rightBegin = leftEnd + 1;
    return ::gcd(
            getGcd(qLeft, qRight, left, leftEnd, (pos << 1) + 1, gcd),
            getGcd(qLeft, qRight, rightBegin, right, (pos << 1) + 2, gcd));
}//O(logN)
 
bool writeOutputData(const std::vector<int> &data) {
    using namespace std;
  
  //открываем файл для записи
  ofstream fout("./output.txt", std::ios_base::out);
 
  if (!fout.is_open())
  {
    cout << "Some error occurred while opening file for writing.\n";
    return -1;
  }
 
  for (auto el : data)
  {
    fout << el << " ";
  }
  fout << endl;
 
  //закрываем файл
  fout.close();
 
  return true;
}//O(N)
 
int main()
{
    std::ifstream inputFile("input.txt");
    std::multimap<int, int> pairLR;
    std::vector<int> outputData;
    int numOfElements, mNum;
    std::vector<int> elements;
 
    if (!inputFile)
    {
        std::cout << "File couldn't be opened for reading";
        inputFile.close();
        return -1;
    }
 
    //читаем кол-во элементов (N)
    inputFile >> numOfElements;
    if (numOfElements <= 0)
    {
        std::cout << "Could not read the number of elements.\n";
        inputFile.close();
        return -1;
    }
    elements.push_back(-1);
    //читаем элементы
    for (int i = 0; i < numOfElements && !inputFile.eof(); i++)
    {
        int tmp;
        inputFile >> tmp;
        elements.push_back(tmp);
    } //O(N)
    //читаем M число
    inputFile >> mNum;
    if (mNum <= 0)
    {
        std::cout << "Could not read M number.\n";
        inputFile.close();
        return -1;
    }
    //читаем M левых-правых пар
    for (int i = 0; i < mNum && !inputFile.eof(); i++)
    {
        int left, right;
        inputFile >> left;
        inputFile >> right;
        pairLR.insert(std::pair<int, int>(left, right));
    }//O(N)
    // закончили читать из файла
    inputFile.close();
 
    std::vector<int> gcdVector(4 * numOfElements, -1);  //создаем вектор gcd, наполненный -1-ми, чтобы потом легче было обнаружить ошибку
    fill(1, numOfElements, 0, elements, gcdVector);
    
    for (auto pair : pairLR)
    {
        int left = pair.first;
        int right = pair.second;
        
        
        int gcdValue = getGcd(left, right, 1, numOfElements, 0, gcdVector);
        //std::cout<<gcdValue<<std::endl;
        outputData.push_back(gcdValue);
    } //O(N)
    
    writeOutputData(outputData);
    
return 0;
}