Wrong TimeComplexity Analyser

[eeshwar369]

include

using namespace std;

class Solution { public: int findgpd(int a, int b) { int ans = 0; for (int i = b; i > 1; --i) { if (a % i == 0) { ans = i; break; } } return ans; }

int minOperations(vector<int>& a) {
    int n = a.size();
    int res = 0;
    int p = a[n - 1]; // Start with the last element

    for (int i = n - 2; i >= 0; --i) {
        if (a[i] > p) {
            res++;
            int t = findgpd(a[i], a[i + 1]);
            if (t == 0) return -1;
            a[i] = t;
            if (a[i] == 1) break;
            p = a[i]; // Update p
        } else {
            p = a[i]; // Update p
        }
    }

    // Check if the array is non-decreasing
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) return -1;
    }

    return res;
}

};

Expecting O(n) time complexity due to single loop but is it so?

[eeshwar369]

Wrong Time Complexity Analyser

[github-actions[bot]]

👋 Thank you for raising an issue! We appreciate your effort in helping us improve. Our CodeIt team will review it shortly. Stay tuned!

[multiverseweb]

Hey @eeshwar369, I understand that the Time Complexity Analyser is noy accurate. But the time complexity of the code in you issue is o(n) and that's what the Analyser is showing? 😕

Would you like to work on this issue? (increasing the accuracy of analyser)

[eeshwar369]

The Issue here is that the time complexity is being analysed only with the loops but the time complexity of functions in it are not getting analysed and yes,I would work to improve the accuracy of this .