# Tag Info

2

A basic result in elementary arithmetic states that $$\log_a n = \log_a b \cdot \log_b n.$$ Indeed, on the one hand, $a^{\log_a n}$ by definition. On the other hand, $$a^{\log_a b \cdot \log_b n} = (a^{\log_a b})^{\log_b n} = b^{\log_b n} = n.$$ Similarly, $$\log_b n = \log_b a \cdot \log_a n.$$ This shows that every two logarithms only differ by a ...

3

The average case running time of quicksort satisfies the recurrence $$T(n) = \frac{1}{n} \sum_{i=1}^n [T(i-1) + T(n-i)] + \Theta(n),$$ with base case $T(0) = \Theta(1)$. In view of solving this recurrence, let us replace $\Theta(n)$ with $n+1$ and $\Theta(1)$ with $2$ (the reason for these specific choices will become apparent below). Changing the order ...

2

Typical implementations of Merge sort use a new auxiliary array split into two parts, a left part and a right part. This extra space is the reason for the O(n) space complexity. During the sort section of the algorithm we have the following two new auxiliary arrays created for additional space. int leftPartition[] = new int[ leftPartitionSize ]; int ...

1

Just to add on to the answer provided by @Yuval Filmus to further illustrate why the pair $Y_{i-1},Y_{n-i}$ should be independent on $Z_{n,i}$. Here is what I got wrong: From $Y_n = \sum_{i=1}^{n} Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))$, I had mistakenly thought that $i$ is a random variable. When I put this back into the definitions: $Z_{n,i}$ denotes ...

0

The idea is that the following two experiments produce the same random variable: A random permutation $\pi$ of $[n]$ subject to $\pi_i = n$. Choose a random subset $S$ of $[n-1]$ of size $i$, a random permutation $\alpha$ of $S$, a random permutation $\beta$ of $[n-1] \setminus S$, and let $\pi = \alpha, n, \beta$. The height of a BST based on the $\alpha$ ...

1

The best way to answer this is to use a profiler, but since I don't have your test cases I've looked around in the code and I'm fairly confident that it's due to differences in the way they produce the paths. The networkx A* implementation uses the standard technique of building a predecessor map and chaining backwards down it when the destination is ...

2

It depends how you implement Dijkstra. The usual description of Dijkstra adds every vertex of the graph to the queue at the start, which is rather inefficient. A* without a heuristic is often called "uniform cost search" (UCS) and the way it's described, you only add vertices to the queue when you discover them. This means that, especially in sparse ...

0

The question is posed badly. The asymptotic execution time of one algorithm is $\Theta(n^2)$, the other is $\Theta(n)$. That means A is asymptotically faster on any implementation. But that’s not the question. The question is “when is A faster”. And that depends on the exact implementation. We can make an educated guess: Both algorithms add up the same ...

1

Algorithm A contains an instruction that is executed $size * 10000$ times. Algorithm B contains an instruction that is executed $size * size$ times. It is obvious that the comparison between A and B depends on the variable size. You can see that if $size < 10000$ then B performs better, and if $size > 10000$ then A performs better. If $size = 10000$ ...

0

I wouldn’t be too happy with your professor’s solution. You noticed that it will refuse to do a very fast counting sort if all item are either nk+1 or nk+2. That’s bad. What is fatal is that it will always do a counting sort if the array elements are all negative. (Please don’t tell me that a sorting algorithm which can only handle positive numbers would ...

0

This result is stated in: Kocsis, L., & Szepesvári, C. (2006, September). Bandit based monte-carlo planning. In European conference on machine learning (pp. 282-293). Springer, Berlin, Heidelberg. It is the content of Theorems 5 & 6. Sadly there is no detailed proof for theorem 5. The main reference for this is: Auer, P., Cesa-Bianchi, N., & ...

2

There is an $O(k\log k)$ algorithm pointed out by this SO answer. Create a sorted list toVisit, which contains the nodes which we will traverse next. This is initially just the root node. Create an array smallestNodes. Initially this is empty. While length of smallestNodes < k: Remove the smallest Node from toVisit add that node to smallestNodes ...

1

A[i..j] is a convention. We could define it any way we like, but we define it in a way that gives useful results. One property is that if we reduce the right index by 1, then we lose the rightmost element. For example, going from A[5..10] to A[5..9] we lose element 10. So what is A[i..i] and what would you expect going from A[i..i] to A[i..i-1]?

0

I try to summarize the results of the discussion in the comments: Using a heap instead of a list would be better suited for the proposed idea since all operations to be performed on the list are sorting, returning the smallest element and changing an element followed by resorting the list. These are almost exactly the operations supported by heaps, which ...

1

It's a convention. One reason for the convention is that the length of an array $A[i..j]$ is $j-i+1$, so if $j=i-1$, we should get an array of length zero. Due to this reason, we sometime consider $A[i..j]$ to be undefined when $j < i-1$; in other cases, the issue does not arise, and $A[i..j]$ is just the empty array whenever $j < i$. In yet other ...

1

Yes, you may consider this as axiom. Or try to make a definition that still works for a > b case - most probably it will give you an empty array in this case. For example, "all elements with indexes i >= a and i < b".

1

This variant decreases number of main loop passes by factor of 2, but in return loop body uses twice workload. Since the change is minor, you can simply read complexity from basic selection sort. The selection sort has this property that number of swaps is at most $n$, finding element to its proper place, so it takes $\mathcal O(n)$ swaps in the worst case. ...

0

Edit: My apologies, misunderstood what you meant by sentinel earlier. It seems to me that you are correct, and this is indeed a typo. When you include comparison against the sentinel at $a[0]$, you perform $i - 1 + 1 = i$ comparisons on a worst case sift.

Top 50 recent answers are included