# Tag Info

9

Don't trust plots. By Stirling's approximation (and dropping the ceilings to avoid notational overload), \begin{align*} (\log n)! &\sim \sqrt{2\pi \log n}\left(\frac{\log n}{e}\right)^{\log n}\\ &= \sqrt{2\pi \log n}\, e^{(\log\log n - 1)\log n}\\ &= \sqrt{2\pi \log n}\, n^{\log\log n - 1}\,, \end{align*} which grows faster than any ...

3

Let's choose $n=2^k$, and see if $T(n)=\lceil\log_2 n \rceil !$ is bounded by a "polynomial of $2^k$" i.e. is $O(2^{mk})$ for some constant $m$. That is, $O({(2^m)}^k)$ for some $m$, or equivalently $O(b^k)$ for some basis $b>1$. In other words, we want to check if $T(n)=T(2^k)$ is bounded by some exponential of $k$. We have  T(2^k) = \lceil\log_2 2^k ...

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

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

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

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

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

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]?

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

1

Your approach is basically correct. However, be sure to pay attention to a few boundary cases besides the general cases for x2>x1 and y2>y1. Initialize the tables on a single square, i.e., dp[x][y][x][y] = (board[x][y] == 0); Compute the case when the table can be on a single column, dp[x1][y][x2][y] = dp[x1][y][x2-1][y] && (board[x2][y] == 0), ...

1

Snook, Counting bases of representable matroids shows that counting the number of maximal linearly independent subsets of columns is $\mathsf{\# P}$-complete. Your problem is probably also $\mathsf{\#P}$-complete. This suggests that you need an enumerative approach. On the other hand, you can efficiently (in theory) approximate the number of maximal ...

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