Does "O(n)" make sense?


  • 2

    I've seen many people say their solution is O(n). I don't think that makes sense. Either you do consider that the number of digits is bounded by a constant and then you'd say O(1), or you really consider the general case of n digits (i.e., something like BigInteger), and then it's not O(n) because of your translation to string and back (or however else you're extracting and recombining the digits). Saying "O(n)" looks like a nonsensical mix of both viewpoints to me.


  • 0
    V

    @StefanPochmann I saw your solutions in another thread, and they are O(n * n), where n is the number of digits. The problem is limited to 9 digits, but I agree that it's incorrectly to say that it takes O(n) or O(1) as you analyze your algorithm when n is approaching the infinity.

    Having said that, there are real O(n) solutions (one way to do it is below), since each digit is limited to [0..9] and we can use O(1) lookup. If digits can be anything, then it will more like O(n * log n).

    int maximumSwap(int num) {
        auto s = to_string(num);
        vector<int> idx(10, -1);
        for (auto i = 0; i < s.size(); ++i) idx[s[i] - '0'] = i;
        for (auto i = 0, j = 0; i < s.size(); ++i) {
            for (j = 9; j > s[i] - '0' && idx[j] == -1; --j) ;
            if (j > s[i] - '0') {
                swap(s[i], s[idx[j]]);
                break;
            }
            if (i == idx[s[i] - '0']) idx[s[i] - '0'] = -1;
        }
        return stoi(s);
    }
    

  • 0

    @votrubac What makes you think that to_string and stoi are O(n)?


  • 0

    @StefanPochmann
    Hi Stefan, I think you are too serious about this problem. :)
    Some problems are bounded on leetcode. Some of those bounds are "small" while some of others are sort of "big". Theoretically, once a problem is bounded, we should say it O(1) cuz the size of the problem is limited. I think it is just for running the OJ. It does not make sense to run some super big test case on this public platform. On the other hand, if we remove this limit, it may be O(n) or O(nlogn), etc. That is the real complexity of the algorithm. Most of people are used to saying something about that rather than considering the limit of n.


  • 0

    @votrubac Is it OK to say the time complexity is O(b*log_b(n)), where n is the given integer and b is the base (e.g., b = 10)?


  • 0

    @Nakanu I think you misunderstood my point. I'm fine with both "O(1)" or "O(n2)" here, I have no issue with either of them. It's just "O(n)" and it's because that simply doesn't make sense.

    You describe the same two views that I had already described. And I'm fine with both of them[*]. But one of these views leads to O(1) and the other leads to O(n2) or maybe something like O(n log2 n log log n). Neither leads to O(n).

    I suspect people simply ignore or don't realize the base conversions and their higher-than-O(n) costs, and I find that worth pointing out.


    [*] Well, in most problems I'd disagree with "O(1)" being fine, because an artificial LeetCode limit of let's say array length to 10000 isn't meaningful and saying "O(1)" based on it would be useless. But for this problem I think "O(1)" would be ok, since the limit rather comes from the languages (their ints being limited to 32 bits), not so much from LeetCode. It's not a limit mentioned just in the notes. It's pretty much encoded by the argument type already. (Yes, the limit is 108 which is lower than what 32-bits ints support, but not by much. Even without the 108 limit we'd have a similar limit, also leading to "O(1)").


  • 0
    P

    @StefanPochmann Regarding this "@votrubac What makes you think that to_string and stoi are O(n)?" Are they not?


  • 0

    @panchajanya I am not quite sure for CPP. But in Java, if u do something like String s = "" + number. It is O(length of the number ^ 2).


  • 0

    @StefanPochmann Ah, I see. Yea, I agree with you at this point.


Log in to reply
 

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