tanmoy
  • Member for 8 years
  • Last seen more than a month ago
$T(n)=2T(n/2)+n\log n$ and the Master theorem
3 votes

Case 3 of Master Theorem: If $f(n)=\Omega(n^{\log_b a+\epsilon})$ for some constant $\epsilon > 0$, and if $f (n/b) ≤ cf (n)$ for some constant $c < 1$ and all sufficiently large $n$, then $...

View answer
I need clarification about DFA's and DFA acceptable languages
1 votes

Acceptance of a Language $L$(regular): means there is a finite accepter that accept all strings $w$ belongs to L and reject all strings not in $L$. An example of a language that is not DFA acceptable ...

View answer
Why is constant always dropped from big O analysis?
Accepted answer
1 votes

Big-O notation only describes the growth rate of algorithms in terms of mathematical function, rather than the actual running time of algorithms on some machine. As growth rate of function $f(n)=n^2$ ...

View answer
Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm?
1 votes

...while calculating time complexity and operations such as swap are ignored You are wrong. All the operations are taken into account when calculating time complexity. But as loops are dominant ...

View answer
Can you reduce a precedence graph or do *all* relevant nodes need to be connected
Accepted answer
4 votes

Yes it is necessary. According to the definition of precedence graph, a directed edge $T_i \longrightarrow T_j$ is created if one of the operations in $T_i$ appears in the schedule before some ...

View answer
Clustered index is dense or sparse?
Accepted answer
1 votes

Clustering index is applied when records are physically ordered on a nonkey field(called clustering field). As clustering field is nonkey so there can be more than one distinct record for a single ...

View answer
How many states when converting CFG to PDA
2 votes

When converting CFG to NPDA ,then to simplify the process, first convert the CFG to Greibach Normal Form(GNF). Now using three states: Qstart, Qloop and Qaccept, you can generate all transition rules ...

View answer
Is this a proper Max Heap Data Structure
Accepted answer
2 votes

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree, the tree is completely filled on all levels except possibly the lowest. Min Heap has the ...

View answer
Why is there a 2n+1 comparison for a linear search algorithm?
Accepted answer
3 votes

procedure last_even_loc(a1,a2,...,an:integers) 1.location = 0; 2.for i = 1 to n 3. if (a_i = 0) (mod 2) then location = i 4.return location; statement 1 is executing only once. statemet 2 is ...

View answer
Why is non-determinism a useful concept?
0 votes

First of all I would like to say thanks to all the people who answered the question.All the answers are important and add some useful information.But as it is a tricky question to the beginners, and ...

View answer
Why does merge sort run in $O(n^2)$ time?
Accepted answer
7 votes

This is actually a mathematical matter and not the matter of the worst case running time. First you have to know that Big O does not represent worst case running time of some algorithms. Big O comes ...

View answer