New answers tagged

0 votes

How far can we push "counting argument" for proving lower bounds of time complexity?

Consider this fictional problem, where you need to test the following property: $\exists i,j$ such that $h(x_i + x_j) = 0$ where $1\le i,j\le n$ and $h(.)$ is a cryptographic hash function. Given that ...
codeR's user avatar
  • 635
0 votes

Ways to speed up a Recursive Backtracking Algorithm

Using Backtracking in the case of a Sudoku puzzle it is possible to prioritize the cells with the greatest amount of cover rather than simply start at one corner. Clearly a cell with a cover level of ...
user169492's user avatar
1 vote

Set partitions and integer partitions

It should help to see that if $(S_1, …, S_k)$ is a set partition for input $(X, n_1, …, n_k)$, then $(S_2, …, S_k)$ is a set partition for input $(X\setminus S_1, n_2, …, n_k)$. Now you just need to ...
Nathaniel's user avatar
  • 15.6k
1 vote

Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?

It depends on the order of the children. It is usually the case that children in rooted trees are browsed from left to right. Also, if the DFS is written recursively, then this is indeed the correct ...
Nathaniel's user avatar
  • 15.6k
1 vote

Proving a statement involving asymptotic notation

Suppose $f(n) = n^2$. Clearly, we have $f(n) \in \Omega(n)$ but $f(n) \notin O(n)$. It does not require the information given for $g(n)$. Had the quotation been to prove/disprove $f(n) \in O(g(n))$, ...
codeR's user avatar
  • 635

Top 50 recent answers are included