New answers tagged arrays
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
