CODEWITHSUNDEEP
c++algorithmc++11time-complexity
akaAbdullahMateen
akaAbdullahMateen

Reputation: 796

Why is time taken by O(NlogN) algorithm same as that of O(N^2)?

I wrote two functions maxSubSum2 and maxSubSum3, both of which try to find the maximum continuous sum of a sub-sequence in a given sequence.

maxSubSum2()

int maxSubSum2(const std::vector<int> &v)
{
    int maxSum = 0;
    for(std::size_t begin = 0; begin < v.size(); ++begin)
    {
        int thisSum = 0;
        for(std::size_t end = begin; end < v.size(); ++end)
        {
            thisSum += v[end];
            if(thisSum > maxSum)
                maxSum = thisSum;
        }
    }
    return maxSum;
}

maxSubSum3()

int maxSubSum3(const std::vector<int> &v)
{
    return maxSumRec(v, 0, v.size() - 1);
}

int maxSumRec(const std::vector<int> &v, std::vector<int>::size_type left, std::vector<int>::size_type right)
{
    if(left == right)
        if(v[left] > 0)
            return v[left];
        else
            return 0;
    std::vector<int>::size_type center = (left + right) / 2;
    int maxLeftSum = maxSumRec(v, left, center);
    int maxRightSum = maxSumRec(v, center + 1, right);
    int maxLeftBorderSum = 0;
    int leftBorderSum = 0;
    for(std::vector<int>::size_type idx = center; idx < v.size(); --idx)
    {
        leftBorderSum += v[idx];
        if(leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }
    int maxRightBorderSum = 0;
    int rightBorderSum = 0;
    for(std::vector<int>::size_type idx = center + 1; idx <= right; ++idx)
    {
        rightBorderSum += v[idx];
        if(rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }
    return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

int max3(int n1, int n2, int n3)
{
    if(n1 >= n2 && n1 >= n3) return n1;
    if(n2 >= n1 && n2 >= n3) return n2;
    if(n3 >= n1 && n3 >= n2) return n3;
    return 0; // <--- Should never happen
}

Because maxSubSum2() has a double nested for loops, its time complexity needs to be O(N), and because maxSubSum3() uses divide and conquer, its time complexity needs to be O(NlogN).

However, I created a simple running time calculation function stopwatch() to measure the actual running time runtime for each function. It looks like the following:

void stopwatch(int (*maxSubSumN)(const std::vector<int>&), const std::vector<int> &v)
{
    std::chrono::time_point start = std::chrono::steady_clock::now();
    maxSubSumN(v);
    std::chrono::time_point end = std::chrono::steady_clock::now();
    std::chrono::duration<double> runtime = end - start;
    std::cout << std::fixed << std::setprecision(9) << std::left << std::setw(9) << runtime.count();
}

Before the program begins, I populate two vectors small and big with 1000 and 10000 randomly generated int respectively; like this:

int randInt()
{
    return std::rand() % 101 - 50;
}

void populate(std::vector<int> &v)
{
    for(int &i : v)
        i = randInt();
}

int main()
{
    std::srand(std::time(NULL));
    std::vector<int> small(1000);
    std::vector<int> big(10000);
    populate(small);
    populate(big);
    std::cout << "[OPTIMIZED BRUTE FORCE] \t: ";
    stopwatch(maxSubSum2, small);
    std::cout << std::endl;
    std::cout << "[OPTIMIZED BRUTE FORCE] \t: ";
    stopwatch(maxSubSum2, big);
    std::cout << std::endl;
    std::cout << "[DIVIDE AND CONQUER] \t\t: ";
    stopwatch(maxSubSum3, small);
    std::cout << std::endl;
    std::cout << "[DIVIDE AND CONQUER] \t\t: ";
    stopwatch(maxSubSum3, big);
    std::cout << std::endl;
    return 0;
}

However, after running the program several times, the execution time for both maxSubSum2 and maxSubSum3 is almost identical. Below are the results on my machine.

small.size() == 10 && big.size() == 100

[OPTIMIZED BRUTE FORCE]         : 0.000001015
[OPTIMIZED BRUTE FORCE]         : 0.000041509
[DIVIDE AND CONQUER]            : 0.000001789
[DIVIDE AND CONQUER]            : 0.000058110

small.size() == 100 && big.size() == 1000

[OPTIMIZED BRUTE FORCE]         : 0.000042093
[OPTIMIZED BRUTE FORCE]         : 0.003870208
[DIVIDE AND CONQUER]            : 0.000053203
[DIVIDE AND CONQUER]            : 0.003899243

small.size() == 1000 && big.size() == 10000

[OPTIMIZED BRUTE FORCE]         : 0.002765456
[OPTIMIZED BRUTE FORCE]         : 0.271172096
[DIVIDE AND CONQUER]            : 0.002931273
[DIVIDE AND CONQUER]            : 0.274476880

small.size() == 1000 && big.size() == 1000000

[OPTIMIZED BRUTE FORCE]         : 0.002730444
[OPTIMIZED BRUTE FORCE]         : 26.383375030
[DIVIDE AND CONQUER]            : 0.002903615
[DIVIDE AND CONQUER]            : 26.508168165

Any help would be highly appreciated. For reference, I am learning from the book: Data Structures and Algorithms in C++ (4th Edition).

Problem solved. Problematic part: use of overflowing integer

See interjay's answer below

for(std::vector<int>::size_type idx = center; idx < v.size(); --idx)

It makes a difference because the loop is only supposed to go down to left but you made it go down to 0. This changes the recursive call's runtime to O(n) instead of O(right - left), and the total runtime to O(n^2) because there are a total of O(n) recursive calls

Credits: interjay

Upvotes: 2

Views: 179

Answers (1)

interjay
interjay

Reputation: 110148

    for(std::vector<int>::size_type idx = center; idx < v.size(); --idx)

This loop doesn't make sense. You're decreasing idx while idx < v.size(), which for an unsigned number is the same as decreasing it until it underflows past 0. That will both increase your asymptotic runtime, and possibly give incorrect results.

You may have intended idx >= left, but that won't work for left == 0 due to using unsigned types, so you may want to use difference_type instead of size_type.

In any case, I suggest making sure that both algorithms give the same results if you haven't done so.

Upvotes: 2

Related Questions