Help!My recursive solution, is it log(n) time complexity?


  • 0
    O

    here is my code

    class Solution {
    public:
        int findMin(vector<int> &num) {
            return findMinRecursion(num,0,num.size()-1);
        }
        int findMinRecursion(vector<int> &num,int l,int r)
        {
            if(l==r) return num[r];
            if(num[l]<num[r]) return num[l];
            else{
                int mid=(l+r)>>1;
                int minL=findMinRecursion(num,l,mid);
                int minR=findMinRecursion(num,mid+1,r);
                return min(minL,minR);
            }
        }
    };
    

    since my code doesn't take fully use of the middle index element, and I used min() function, it's different from other's code. I'm confused, is it log(n) time complexity?


  • 0
    B

    I think the time complexity is n/2 + n/4 + n/8+... = O(n)


  • -5
    T

    Yes, The time complexity is log2(n)


  • 2
    L

    it is O(N) in the worst case for 1,1,1,....,1 as u visit every element.


  • 0
    I

    that is right O(n)
    not O(logn)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.