2

Try it like this: "we can pick a constant $C$ such that, for sufficiently large $n$, $T(n)$ will always be less than $Cf(n)$". Intuitively, this does indeed mean that lower-order terms and constant factors don't matter. Because lower-order terms stop mattering once $x$ gets sufficiently large, and constant factors can be cancelled out by an appropriate ...


1

Your algorithm makes $\lfloor \log n \rfloor+ 1$ comparisons for an array of length $n$, which is at most $2 \log n$, which is $O(\log n)$. Hence, $\lfloor \log n \rfloor+ 1 = O(\log n)$. In more detail, recall that the big-O notation subsumes constant factors. A function $f(n)$ is said to be $O(\log n)$ if there exist positive constants $c$ and $n_0$ ...


1

I believe a hashing approach should give you $O(N)$ time, where $N$ is the length of the longer array (we can relax the constraint that they are the same size). Simply put all the elements in the first array into a hashset, and then check whether each element in the second array exists in the hashset. You could even account for duplicates by instead using ...


Only top voted, non community-wiki answers of a minimum length are eligible