Skip to content

Instantly share code, notes, and snippets.

@kephin

kephin/answer2.md

Last active August 15, 2017 14:56
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kephin/cd2166931a4aacba3eb4dc6671b8a3c4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kephin/cd2166931a4aacba3eb4dc6671b8a3c4 to your computer and use it in GitHub Desktop.
Download ZIP
Computational complexity of the answer in Question 1
Raw
answer2.md

Question 2

What is the computational complexity of your answer in Question 1? Can you explain why?

  • O(n^2)
  • O(nlogn)
  • O(n)
  • O(logn)

Answer:

O(n^2), The worst case would be if the 2nd array is the subset of the 1st array; In that case, we should go all over every item of the 1st array to check for every item of the 2nd array, which takes a * b steps (a: length of the 1st array, b: length of the 2nd array). So the space complexity would be O(n^2)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment