# Tag Info

4

I believe the goal of this question was to get you to say that the information about even or odd can't lead to any significant speedup in runtime. Suppose you have an algorithm which works very fast in that case. Then, given any array of integers, you can split it up into an array of even integers and an other of odd integers in linear time. You can then ...

3

Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values). Let say we know that all integers in $A$ are 32-bit values. Use the following steps: Create an empty trie. Every node of trie may contains at most two children for 0 and 1 bits. Insert all values in $A$ into ...

3

Both of them will work, and both of them support insertions${}^1$ and deletion${}^2$ of the minimum element in $O(\log n)$ worst-case time (where $n$ is the number of elements currently in the data structure). It really depends what you mean by "better". An AVL tree will have the additional binary-search-tree property that the heaps do not have, and this ...

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 ...

1

An algorithm can be seen as the steps needed to go from a well defined type of input to some well defined output. The input can therefore be everything that one can represent within a computer. In the algorithm you are asking for it seems like the input has already been classified as specific good as in apples are already classified as apples, had it not ...

1

That's because you only have a constant number of elements, in this case 100. In other words, $100^2 = O(1)$, i.e., you do a constant amount of work. Usually it is more interesting to analyze the scalability of an algorithm with a growing input size $n$.

1

No it is not. They both have the same running time but the heap is way lighter for a couple of reasons. For the asymptotic running time, note that a heap can be built in linear time meanwhile applying $n$ operations of extract min takes a total of $O(n \log n)$. On the other hand, constructing an AVL tree requires $O(n\log n)$ operations meanwhile traversing ...

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