time complexity of this problem "Asymptotic Running Time Discrepancy: O(nlogn) vs O(n) Using Master Theorem

Question

Consider the following procedure, which takes as input an array A. What is the asymptotic running time of printStuff subroutine?

here I have done normal method step by step calculation, I got O(nlogn) but while using the master method I'm getting O(n) so what is the correct answer

Here the work i have done
The length of the array 'A' is 'n'.
If 'n' is equal to 4 or less than 4, then the function returns immediately. Therefore, this operation takes constant time, so the time complexity is O(1).

If 'n > 4', the algorithm prints all elements of the array 'A'.
Since the loop iterates over all 'n' elements, this operation takes O(n).

From Recursive Calls: There are two recursive calls in the function:

One on the first quarter of the array: printstuff(A[n/4:]) The other on the last quarter of the array: printstuff(A[3n/4:]) Recurrence Relation: The work done by the function to print all the elements of the array is O(n).

There are two recursive calls: one on a subarray of size n/4 and another on a subarray of size 3n/4.

From this recurrence relation: T(n) = T(n/4) + T(3n/4) + O(n)

Solving the Recurrence Relation:

Initial Work at Level 0: T(n) = O(n)

Work at Level 1: The work done by the two recursive calls is: T(n/4) + T(3n/4) Thus, the total work at level 1 is: T(n/4) + T(3n/4) + O(n)

The total work at Level 1 = O(n).

Work at Level 2: At this level, the recursive calls from T(n/4) and T(3n/4) split into smaller parts: T(n/16) + T(3n/16) + T(3n/16) + T(9n/16) + O(n) So, the total work done at this level adds up to O(n). The total work at Level 2 = O(n). This process continues until 'n' is less than or equal to 4.

Recursion Tree: The depth of the recursion tree is determined by how many times we can divide the problem size before it becomes n ≤ 4. Since we are reducing the problem size by factors of 1/4 and 3/4 at each step, the depth of the recursion tree is O(log n).

Thus, the total work is: O(n) × O(log n) = O(n log n)

Conclusion: The overall time complexity of the algorithm is O(n log n).

Answer 1

It's O( n )

here is why:

Let's simplify the function a little bit:

this will take the same time it's just that the array will be printed in another order

Anyway let's compute the complexity:

firstly it will print from 0 to n,

then it will print from 0 to n/2

then from 0 to n/2/2 (n/4), and so on.

so it will be:

n + n/2 + n/4 + n/8 + n/16...

1/2 + 1/4 + 1/8 + 1/16... is mathematically proven to be = 1

so the complexity will be n + n -> 2n -> n

so it's:

O(n)

Here is a program in c++ that tests the algorithm and the comparison between both cases (two 1/4 calls or one 1/2 call) and you can play around with it as you want for sure:

#include <iostream>;
using namespace std;
int time2 = 0;
int time4 = 0;

int printStuffBy2(long double* a, long long len) {
    if (len <= 4) {
        return 0;
    }
    for (int i = 0; i < len; i++) {
        //cout << a[i] << endl;
        time2++;
    }
    //cout << endl;
    long double* tempA = new long double[len / 2];
    for (long long i = 0; i < len / 2; i++) {
        tempA[i] = a[i];
    }
    
    printStuffBy2(tempA, len / 2);
    return 0;
}

int printStuffBy4(long double* a, long long len) {
    if (len <= 4) {
        return 0;
    }
    for (int i = 0; i < len; i++) {
        //cout << a[i] << endl;
        time4++;
    }
    //cout << endl;
    long double* tempA = new long double[len / 4];
    for (long long i = 0; i < len / 4; i++) {
        tempA[i] = a[i];
    }

    long double* tempA2 = new long double[len / 4];
    long long j = 0;
    for (long long i = (3 * len / 4); i < len; i++) {
        tempA2[j] = a[i];
        j++;
    }

    printStuffBy4(tempA, len / 4);
    printStuffBy4(tempA2, len / 4);
    return 0;
}

int main() {
    long double len = 10000000;
    long double* a = new long double[len];
    for (long long i = 0; i < len; i++) {
        a[i] = i;
    }
    printStuffBy2(a, len);
    printStuffBy4(a, len);

    cout << endl << time2 << endl << time4;

    return 0;
}