(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.
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\$