Consider a simple function: (where
b are integers)
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.