Prove or disprove that time complexity of the algorithm is O(n)

Question

I was solving this problem on Leetcode and came up with the following solution in C++:

class Solution {
private:
 void nextGreaterElements(const vector<int>& nums, vector<int>& result, int pos) {
 if (result[pos] != numeric_limits<int>::min()) {
 return;
 }
 result[pos] = -1;
 int nxt = (pos + 1) % nums.size();
 while (nxt != pos && nxt != -1) {
 if (nums[nxt] > nums[pos]) {
 result[pos] = nxt;
 break;
 }
 nextGreaterElements(nums, result, nxt);
 nxt = result[nxt];
 }
 }
public:
 vector<int> nextGreaterElements(vector<int>& nums) {
 vector<int> result(nums.size(), numeric_limits<int>::min());
 for (int i = 0; i < nums.size(); i++) {
 if (result[i] != numeric_limits<int>::min()) {
 continue;
 }
 nextGreaterElements(nums, result, i);
 }
 for (int& val: result) {
 if (val == -1) {
 continue;
 }
 val = nums[val];
 }
 return result;
 }
};

The algorithm computes the next greater element for each element in a circular array using memoization and recursive traversal. For each element starting at position pos, it checks subsequent elements (wrapping around circularly) to find the first larger value, storing the result as an index in a memoization array. If the next element is not greater, it recursively resolves the next element's next greater index and jumps directly to that precomputed index, avoiding redundant checks. Once all indices are resolved, the final result is generated by replacing indices with their corresponding values, leaving -1 where no greater element exists.

I'm struggling to model the number of operations to prove that the time complexity is O(N).

• Emil Jeřábek: Well, either way, there is a much simpler solution that needs neither recursion nor memoization. So you should probably think more about the solution strategies.
• donkey: Simplicity is subjective. The posted solution was the first one that I came up with after the brute force one. But that is not the point. I am just curious to determine the complexity

Answer 1

Rotate nums such that the last element is also the greatest. Consider the set of indices of matches between nums and the array of prefix maxima of nums. For consecutive indices $i, j$, $i$ maps to $j$ in $O(j-i)$ steps, and $n$ maps to $-1$ in $O(n)$ steps. By recursively applying this to the subarrays nums[i+1...j], it can be shown that the time complexity is $O(n)$.