0

I had previously mistakenly asked for str.count, when I really meant str.length. Thanks to responders for getting back to me

Is this a constant time operation or linear time? I know in Java it's constant time and C it's linear time, according to In Java, for a string x, what is the runtime cost of s.length()? Is it O(1) or O(n)? but not sure what the case is in Ruby.

Community
  • 1
  • 1
segue_segway
  • 1,490
  • 1
  • 22
  • 40
  • 1
    Why not check their source? – Andrew Li Jan 04 '17 at 00:54
  • 1
    The source only tells you what one specific version of one specific implementation does. It doesn't tell you anything about the guarantees that are made by the language specification. There are about 5 Ruby implementations in the wild right now, I believe. (Well, there are many more, but 5 that are industrial-strength, production-ready, still maintained and developed, and in actual real-world use.) – Jörg W Mittag Jan 04 '17 at 00:58
  • 4
    Do you really mean `String#count`, as your title asks, or do you mean `String#length`, as the linked question suggests? – pilcrow Jan 04 '17 at 01:04
  • 1
    One really great way to feel confident about the answer to this for your own particular use case is to use Ruby's benchmarking tools, outlined here: https://ruby-doc.org/stdlib-1.9.3/libdoc/benchmark/rdoc/Benchmark.html – gdpelican Jan 04 '17 at 04:22

2 Answers2

2

String#count counts the number of occurences of (a set of) substrings in the string. In order to do this, it must compare each character against the predicate set, there is no other way.

It cannot possibly be faster than O(n). The trivial implementation is O(n), so in order to make it slower than O(n), you have to be extra stupid and do extra work. So, since it cannot be faster than O(n), and we can assume that nobody would be stupid or malicious enough to deliberately make it slower than O(n), we can safely conclude that it is O(n).

However, that is just a conclusion. It is no guarantee. The Ruby Language Specification does not make performance guarantees. But you can be pretty sure that a Ruby implementation where it is not O(n) would be ridiculed and simply not used and die.

Jörg W Mittag
  • 363,080
  • 75
  • 446
  • 653
  • 1
    Not quite, it does not count substrings but the occurrences of characters from the intersection of all parameters. Weird, I know. – akuhn Jan 04 '17 at 01:54
  • @akuhn It's a lot like [`String#tr`](https://ruby-doc.org/core-2.4.0/String.html#method-i-tr) that way with that Perl-inspired notation. – tadman Jan 04 '17 at 02:40
  • It actually uses `tr_find` and `tr_setup_table` internally. – akuhn Jan 04 '17 at 03:56
1

The complexity is O(n + m)

Where n is the size of the string and m is the number of character set parameters.

  • O(m) for the creation of the lookup table/hash from the arguments
  • O(n) * O(1) for the comparison of the input string with the lookup table/hash
  • Depending on receiver and arguments, either n or m can be the dominating factor.

If however you mean String#length then it is O(1)

akuhn
  • 27,477
  • 2
  • 76
  • 91