New answers tagged

0

num_to_arr(num): length_of_arr = log(num)+1 //log(num) base 10 arr[length_of_arr] digit = 0 while num > 0: digit = num % 10 arr[length_of_arr - 1] = digit length_of_arr = length_of_arr - 1 num = num / 10 return arr This should do the job.


1

The running time is expected $O(n)$ for both problems. Simply scan over the input list, and as you examine each item, add it to the hashtable; if it wasn't already present, output it. The running time is $(n)$ because, with a suitable hash function, the expected time it takes to insert or look up an item in a hash table is $O(1)$. The worst-case running ...


11

What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound. The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2*N* - 1 seems more like it would be the upper bound since there is ...


6

The authors meant "show that any algorithm makes at least $2N-1$ comparisons in the worst case". See Toms answer and comments for an explanation.


Top 50 recent answers are included