# Can I solve my decision problem in $O(n)$ time?

My algorithm solves a custom string problem but it loops twice making it $$O(n^2)$$ time. I'm asking here as I'm a beginner in self-learning algorithms.

Decision Problem: Given an input list $$A$$, can our target string $$S$$ be made from any of the elements of $$A$$?

If just one element does not exist in $$A$$ (which exists in $$s$$) then the algorithm returns false.

A = input_array
s = input_target_array

for i in s:
if i in A:
(all elements ∈ s) ∈ A
else:
break

(if any element ∈ s) ∉ A:
return False
else:
return True


Output

Enter your input for A and include spaces:
Enter letters WITH SPACES: "ab" "cd" "ac"
"abxd"
^ False ^
"abcd"
^ True ^


I'm looking for an algorithm that solves my made up decision problem faster than $$O(n^2)$$ time.

## Question

Are there any methods that can be used from an algorithmic standpoint that would make this $$O(n)$$ time?

• How large is the alphabet? Should we treat the size of the alphabet as constant ($O(1)$) or not?
– D.W.
Jan 22 '20 at 6:04
• @D.W. The alphabet could be any of the infinite ones out there. Sometimes I use smiley faces and pineapples as a character string. Jan 22 '20 at 12:15
• what does (all elements ∈ s) ∈ A mean in code? Jan 22 '20 at 12:55
• – D.W.
Jan 22 '20 at 16:09
• @user253751 Suppose that you see that the elements in $s$ as in the output example contains a character x. Since $A$ does not contain a character x then "(if any element ∈ s) ∉ A" is True (algorithm returns false). Jan 22 '20 at 22:14

I use set difference to find out if there are any elements in $$s$$ that don't exist in $$A$$. This should be $$O(n)$$ in the best cases if there is a good hash. Since I'm dealing with integers it should be $$O(n)$$ Explained here

I then use $$len(s)$$ and $$len(A)$$ which takes $$O(1)$$ time according to here.

A = [1,2,3,4,9]
s = [1,2,3,4,9]

elem_not_in_A = set(s) - set(A)

if len(s) >= len(A):
if len(elem_not_in_A) > 0:
output False
else:
output True
else:
output False


If the set difference remains $$O(n)$$ and all the other statements remain $$O(1)$$ then yes it can be solved in $$O(n)$$ time.