How strict are we with [restricted-complexity]?

Question

(mostly for restricted-complexity. For fastest-algorithm 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 restricted-complexity 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.

Answer 1

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.