Why TLE, could someone help?


  • 0
    R

    The method I'm using is under assumption that we are returning the floor(integer) of the actual squareroot value. The idea is from 1 to x/2, I test if i * i > x, if so, return i-1;

    Time should be: O(m), m is the value I need to scan, but since m^2 <= x, m <= log(x), so time is: O(log(x)).

    But I still got TLE error when x is large, could someone help?

    if(x <= 0) return 0;
    if(x == 1) return 1;
    
    int i = 1;
    for(; i <= x/2; i++){
        if(i*i > x){
            return i-1;
        }
    }
    return i; // It should never run into this line;

  • 1
    R

    Your solution is actually "Linear". You are trying from 1,2,3,4,5... to i
    You should design some algorithm that discard half of the interval each iteration, which leads to O(log(x)) solution.


  • 0
    V

    Above algorithm is linear in time complexity relative to input size, because the loop is traversed until loop index (i) becomes half of input (x).

    But the constant 1/2 gets ineffective when doing asymptotic analysis as the time complexity is measured for very large input size of x

    It is essentially doing linear search. As the algorithm has O(n) time complexity it leads to TLE error for large input size. To make it logarithmic in time complexity need to use the binary search method.

    class Solution {
    public:
    int sqrt(int x) {
        //use binary search instead of linear search the bound is from 0 to INT_MAX
        int end = INT_MAX;
        double begin = 0;
        double temp;
        double mid = (begin + end) / 2;
    
        while(begin <= end){
            temp = mid * mid;
    
            if(temp == x )
                return mid;
            else if(temp > x)
                end = mid - 1;
            else 
                begin = mid + 1;
            mid = (begin + end)/2;
        }
        return mid;
    }
    };
    

  • 0
    R

    Thank you for replying me~!
    But if I set x=100, I actually only scanned 1---11, if I set x=10000, I only scanned 1---101, which is not linear to x. IT's actually O(logx). Anything wrong with this logic?


  • 0
    R

    Thank you for replying me~!
    But if I set x=100, I actually only scanned 1---11, if I set x=10000, I only scanned 1---101, which is not linear to x. IT's actually O(logx). Anything wrong with this logic?


  • 0
    K

    because the number ii overflow in line if(ii > x), and you may not get expected i*i


Log in to reply
 

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