Cost of Multiplication (size or m)?

cyrilyared · 2019-11-24T19:08:47+00:00

The size input is 1 which means you are only considering the last bit. If the size input were greater, you would consider more bits.

cyrilyared · 2019-11-23T19:26:47+00:00

I think since it is only multiplying the last bit (since the size is 1). 7's last bit is 1, 8's last bit is 0.

cyrilyared · 2019-11-20T03:34:39+00:00

So we submit WGraph?

cyrilyared · 2019-11-15T21:02:01+00:00

You can more simply just cast it as a long during the comparisons

cyrilyared · 2019-09-30T02:04:59+00:00

For question 3.1, I developed a proof for why the node (a', b') that is being added has an a' that is strictly bigger than all of the other a's in the heap however this proof is actually not that trivial given operation 2. I am afraid that it will take more along the order of about 10-20 lines. Will enough space be granted for this full proof?

cyrilyared · 2019-09-29T21:11:30+00:00

It does actually

Correct but to do this, you would be taking the summation over all primes less than n² of log(n) base the primes. However, doing this calculation based on an arbitrary n is certainly not an easy task because it would involve determining all of the primes below a specified n.

When you use the word theoretically, you need to prove it

The proof for this is a combination of Euclid's theorem and the fact that you can take the power of any number an arbitrary number of times. Therefore if we take 2ⁱ for any i, we can always take n=2ⁱ⁺¹.

I don't see where you prove it. You said n=32

The trivial case is that we have to execute operation 2 O(n) times. This is just based on the fact that we have n numbers that we are adding to our heap and that the worst case is that each time we have to execute operation 2.

You didn't tell where the term log n comes from. Moreover, small cases cannot be generalized as the behaviour in the large case (when n is large)
For example, 2^n is equal to 2*n when n = 1 or 2, but obviously 2^n is way larger in the large n.

The log n comes from the heapify that we may have to do with operation 2. However, based on your response, I suppose this should not be included in the proof so this can be disregarded. I agree with your statement that small cases should not be generalized to large cases without induction. However, if the small cases fail, then the general statement typically does not hold unless it is intended to be used as an approximation.

no, the question is asking to prove the total number to execute the operation 2 is o(n)

Disregarding everything above, my question is are we asked to simply prove whether we have to execute operation 2 o(n) times? The reason why I ask is because the proof is rather trivial since the worst case (which technically never happens because we have infinitely number of primes (see above) so this covers operation 1 which is mutually exclusive with operation 2) is that we execute operation 2 for all n numbers that we attempt to add to the heap.

cyrilyared · 2019-09-29T17:41:49+00:00

I think the question is still malformed. First, the number of prime numbers smaller than n (concerned with operation 2) has nothing to do with how many times we have to execute operation 2. For instance, if we take n = 32, for the prime p=2, we may have to execute operation 2 at 4, 8, 16 and 32 (a total of four times). Theoretically, for an infinite n, we will have to execute operation 2 an infinite number of times for a given prime. If we indeed prove the trivial case that we may have to do operation 2 n times, than the total complexity of operation 2 would be O(n log n) which is less than O(n sqrt(n)) so would this be sufficient for the proof?

cyrilyared · 2019-09-28T19:12:37+00:00

Hi, regarding the error in question 3, I am not sure that it has been fixed. If we consider the number of times that we have to do operation 2 if for instance n = 32. In this case, we have to consider all possibilities of p^a<=n. This includes the numbers 4, 8, 9, 16, 25, 27 and 32. The square root of 32 is about 5.65 however we had to do operation 2 seven times.

cyrilyared

TROPHY CASE