2
$\begingroup$

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"
enter your input for s:
 "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?

$\endgroup$
  • 2
    $\begingroup$ How large is the alphabet? Should we treat the size of the alphabet as constant ($O(1)$) or not? $\endgroup$ – D.W. Jan 22 at 6:04
  • $\begingroup$ @D.W. The alphabet could be any of the infinite ones out there. Sometimes I use smiley faces and pineapples as a character string. $\endgroup$ – Travis Wells Jan 22 at 12:15
  • 1
    $\begingroup$ what does (all elements ∈ s) ∈ A mean in code? $\endgroup$ – user253751 Jan 22 at 12:55
  • 1
    $\begingroup$ stackoverflow.com/q/4642172/781723, cs.stackexchange.com/q/95996/755 $\endgroup$ – D.W. Jan 22 at 16:09
  • $\begingroup$ @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). $\endgroup$ – Travis Wells Jan 22 at 22:14
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.