4 Replies
      Latest reply on Sep 9, 2019 6:25 PM by QuinceyMorris
      iphonegamedeveloper Level 1 Level 1 (0 points)

        I believe time complexity for rangeOfString:options method is O(n) and for componentsSeperatedByString is also O(n). If its correct, please let me know whether any method available with better time complexity.

        • Re: Time complexity
          Claude31 Level 8 Level 8 (6,495 points)

          Do you have a performance issue ? Could you explain the use case ?

           

          BTW, where did you find that those func were O(n) ? n being the number of chars ?

           

          Would testing if substring is contained in string and only perform rangeof in this case help improve ?

          There could be some improvement if substring is rarely in string.

            • Re: Time complexity
              iphonegamedeveloper Level 1 Level 1 (0 points)

              Use case: Text file contains n number of lines, each line will have URL string. Need to read each line and check for specific host

              So, using componentsSeperatedByString:@"\n" to break each line and iterating array to check whether the URL has specific host(rangeOfString:@"https:xyz.com"options).

               

              I wanted to know the time complexity of those two methods. I don't know these two method's implementation but my guess in its O(n) as it has to check each char whether it matches with given string.

            • Re: Time complexity
              PBK Level 7 Level 7 (3,235 points)

              I would guess that componentsSeparatedByString is of greater order because it has to do the rangeOfString multiple times in order to break the original string into components.  So in your use case, searching for the particular string will be faster.    

              • Re: Time complexity
                QuinceyMorris Level 8 Level 8 (6,020 points)

                I'm not an expert on this, but the order of complexity of both proposed APIs is worse than O(n). I've got a feeling it's something like O(n log(n)) or even O(n squared). If you want to minimize the time, and the separator you're actual searching for is "\n", then I'd suggest using "componentsSeparatedByCharactersInSet:" and specify the new-line character set. That should be actually O(n).

                 

                Keep in mind, though, the the Obj-C APIs provide no order-of-complexity guarantee, unlike the Swift String APIs. The performance may differ between device classes, and OS versions.

                 

                The other possible approach would be to use NSScanner. It may or may not do better with tasks like this.

                 

                However, of course, don't try to solve your performance "problem" until you're sure you have a performance problem, and then actually measure the performance of the approaches you want to compare.