1
\$\begingroup\$

(mostly for . For it's the algorithm that matters, not the code. Answers without code are allowed.)


Consider a simple function: (where a and b are integers)

lambda a,b:a+b

What should be the time complexity of this function?

  • If it's O(log(a)+log(b)), most of the current challenges are impossible. For example this.
  • If it's O(1), that opens too much rooms for abuse. For example you can manipulate strings (with fixed alphabet with size A) in O(1), by using its base-A representation.

Example of a possible abuse, assuming the consensus is all arithmetic operations take O(1):

Given a string s consisting of characters in range ['a' .. 'i']. We can do the following:

def encode(s):
 a=0
 for ch in s:
  a=a*10+ord(ch)-96
 return a

That way the characters in s are encoded into a ('a' -> 1, 'b' -> 2, ..., 'i' -> 9). Assume arithmetic operations take O(1), this takes linear "time". For example if s == 'abcdedcba', a == 123454321.

Now checking whether two substrings of s are equal can take constant "time". Like this:

encode(s[i:]) == encode(s)//10**i
encode(s[:i]) == encode(s)%10**i
encode(s[a:b]) == encode(s[:b][a:])
(s[a:b] == s[c:d]) == (  encode(s[a:b]) == encode(s[c:d])  )

Note that the right hand sides can be evaluated in constant number of arithmetic operations.

Similarly it's possible to check if a substring of a string is palindromic in constant "time", with linear "time" preparation.

\$\endgroup\$
4
  • \$\begingroup\$ (depends on the answers I may or may not post some subsequent questions) \$\endgroup\$
    – DELETE_ME
    Jun 5, 2018 at 15:41
  • \$\begingroup\$ Can you give a more specific example for what abuse is possible if you treat strings in an alphabet of size A as numbers in base A having a number of digits equal to the string's length? Just saying "manipulate strings" doesn't mean much. \$\endgroup\$ Jun 5, 2018 at 19:41
  • \$\begingroup\$ @KamilDrakari Done. \$\endgroup\$
    – DELETE_ME
    Jun 6, 2018 at 2:16
  • \$\begingroup\$ For fastest-algorithm it's the algorithm that matters, not the code. it still makes the space for such thing, and give low theoretical complexity but meaningless solutions \$\endgroup\$
    – l4m2
    Jun 7, 2018 at 6:36

1 Answer 1

4
\$\begingroup\$

Consider a simple function:

lambda a,b:a+b

What should be the time complexity of this function?

I don't think a simple answer to this is possible. It depends on the context. If a and b are strings then it's O(n). If a and b are fixed-width integers then it's O(1). If a and b are explicitly big integers and the question says that arbitrarily large inputs must be handled then it's O(lg n). And if a and b are big integers because that's the language's only integer type, but the question doesn't say anything about input ranges, then I think it should be considered O(1) for fairness because that's what it would be if ported directly to a language with fixed-width integers.

  • If it's O(1), that opens too much rooms for abuse. For example you can manipulate strings (with fixed alphabet with size A) in O(1), by using its base-A representation.

Here I disagree strongly. You can manipulate strings of a bounded length in O(1) (or O(k) where k is the bound), but any answer which claims to manipulate arbitrary-sized strings in O(1) time should receive a comment, a downvote, and a delete vote after the OP has had time to correct it and hasn't done so.


Minor observations:

Example of a possible abuse, assuming the consensus is all arithmetic operations take O(1):

This is actually a stronger assumption than the one you had previously asked about. Even if we were to say that addition of integers is always O(1), that doesn't imply that exponentiation of integers is O(1).

Similarly it's possible to check if a substring of a string is palindromic in constant "time", with linear "time" preparation.

It's not immediately clear why this would be a problem. O(n + lg n) = O(n + 1). If you're doing more than O(n / lg n) subpalindrome checks, there are probably data structures which make those checks more efficient.

\$\endgroup\$
3
  • \$\begingroup\$ Actually palindromic check (with naive algorithm) should take linear time in length of the string. \$\endgroup\$
    – DELETE_ME
    Jun 6, 2018 at 6:28
  • \$\begingroup\$ (about a and b being strings: fixed) \$\endgroup\$
    – DELETE_ME
    Jun 6, 2018 at 6:29
  • 2
    \$\begingroup\$ @user202729, yes, but what's your point? Linear time preparation then constant or logarithmic time processing is not asymptotically better than no preparation and linear processing. \$\endgroup\$ Jun 6, 2018 at 6:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .