Problem Detail: what is the complexity of below relation $ T(n) = 2*T(sqrt n) + log n$ and $T(2) = 1$ Is it $Theta (log n * log log n)$ ? Asked By : panthera onca Answered By : Ken P Yes, the Read More …
Author: ignougroup
[Solved]: Equivalent Straight Line Embedding of a Planar Graph Drawing on a Grid
Problem Detail: An embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that: the Read More …
[Solved]: Counting inversion pairs – $n^2$ results in $n log n$ time?
Problem Detail: The number of possible inversions in an array is bounded by $binom{n}{2}$, i.e $frac{n(n-1)}{2} in O(n^2)$. How it is possible to calculate $O(n^2)$ results in $O(nlog n)$ time using something like modified merge sort? (sample algo : http://www.geeksforgeeks.org/counting-inversions/). Asked Read More …
[Solved]: Decrease space complexity, how will time complexity increase?
Problem Detail: I have a problem whose lower bound of problem complexity is proven to be $O(n+m)$ (n < m) and I also come up with an algorithm whose time complexity is $ O(n+m)$, space complexity is $ O(n)$. (All on Read More …
[Solved]: Undecidability in the context of modern programming languages
Problem Detail: Imagine a program, executed by an interpreter to be a Turing Machine. Consider this code: x = read_input print x Does undecidability mean that there may possibly be an input to this program such that the program may never Read More …
[Solved]: Is the memory-runtime tradeoff an equivalent of Heisenberg’s uncertainty principle?
Problem Detail: When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, but I can Read More …
[Solved]: Is this path finding problem in a 01-matrix NP-complete?
Problem Detail: The problem: Input: An $n times n$ matrix of 0’s and 1’s, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 leq i,j leq n$) Output: YES if there exists a path Read More …
[Solved]: Why do we use Insertion Sort in the Bucket Sort?
Problem Detail: Bucket sort is a linear-time sort. Why do we use insertion sort in it? We know that insertion sort takes $O(n^2)$ time. Why can we not use any linear sort inside it? As we see, when in each bucket Read More …
[Solved]: Confusion in CLRS’s version of Prim’s algorithm
Problem Detail: The algorithm is as follows: MST-PRIM(G,w,r) 1 for each u ∈ G.V //initialization 2 u.key = ∞ 3 u.π = NIL 4 r.key = 0 5 Q = G.V //end initialization 6 while Q ≠ ∅ 7 u = Read More …
[Solved]: Generating constraints to solve dependently-typed metavariables?
Problem Detail: In dependent-types, Miller pattern unification is used to solve a decidable fragment of higher-order unification. This allows dependently-typed languages to contain metavariables or implicit arguments. There are many papers which describe, given a unification problem in the pattern fragment, Read More …
