Register
Webpage for Algorithms

Recent questions tagged algorithms

2 votes
1 answer
1981
time complexity
If F(n) = (log n)n then, is F(n) = O(n2) true? Also, what about F(n) = $\Theta$(n2)
If F(n) = (log n)n then, is F(n) = O(n2) true?Also, what about F(n) = $\Theta$(n2)
User Avatar
0 votes
1 answer
1982
time complexity
a[] is an array of integer, the size of the array is n. Read the following code snippet and find the time complexity of the code. int main(){ int i,j,k=0; for(i=0;i<n;i++){ for(j=0;j<i;j++){ while(k<i && a[j]<a[k]){ k++; } } } }
a[] is an array of integer, the size of the array is n.Read the following code snippet and find the time complexity of the code. int main(){int i,j,k=0;for(i=0;i<n;i++)...
User Avatar
1 votes
0 answers
1983
Virtual Gate Test Series: Algorithms - Tree Coloring
Consider a tree with $n$ nodes where a node can be adjacent to max $4$ other nodes what is the minimum number of colors needed to color the tree so that no two adjacent nodes get the same color?
Consider a tree with $n$ nodes where a node can be adjacent to max $4$ other nodes what is the minimum number of colors needed to color the tree so that no two adjacent n...
User Avatar
3 votes
0 answers
1985
cormen
Show that a graph has a unique minimum spanning tree if, for every cut of the graphs, there is a unique line edge crossing the cut. Show that the converse is not true by giving a counter example. I'm more interested in the converse. Please explain in detail.
Show that a graph has a unique minimum spanning tree if, for every cut of the graphs, there is a unique line edge crossing the cut. Show that the converse is not true by ...
User Avatar
1 votes
2 answers
1987
Asymptotic notations
g(n)=Ώ(n) h(n)=O(n) g(n) . h(n) =?
g(n)=Ώ(n)h(n)=O(n)g(n) . h(n) =?
User Avatar
3 votes
3 answers
1988
Quick Sort
"Quick sort has good cache performance" , Can anyone explain this statement.How is cache related to quick sort.I searched for this over the internet but could not find a good article.
"Quick sort has good cache performance" , Can anyone explain this statement.How is cache related to quick sort.I searched for this over the internet but could not find a ...
User Avatar
1 votes
1 answer
1989
True/False?
The depth of any DFS (Depth First Search) tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex. I think in line graph has the same depth in both DFS and BFS. So it may be false.
The depth of any DFS (Depth First Search) tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex.I think in line graph has the...
User Avatar
1 votes
2 answers
1990
Algorithms
Solve this T(n) = 0.5T(n/2)+1 ; T(1)=1
Solve thisT(n) = 0.5T(n/2)+1 ; T(1)=1
User Avatar
0 votes
0 answers
1991
Interview
Have to find MAX of aj-ai in an array where j>=i+l in linear time.How to do it?My approach is to start j from l+1 to n and check min element every time is it a correct way to do it? when j = l+1 we check only 1st elemrent and for j = l+2 next 2 element and so on Is this approach is right?
Have to find MAX of aj-ai in an array where j>=i+l in linear time.How to do it?My approach is to start j from l+1 to n and check min element every time is it a correct wa...
User Avatar
1 votes
3 answers
1992
Time Complexity of Iterative Program
The innermost loop will execute when j is multiple of i, and that will happen exactly i times. Please help me to find the time complexity of the below program:
The innermost loop will execute when j is multiple of i, and that will happen exactly i times. Please help me to find the time complexity of the below program:
User Avatar
0 votes
1 answer
1993
Analysis of Algorithms (Recurrences)
Consider the following recurrence. T(n) = T() + What is the value of recurrence? please explain in detail
Consider the following recurrence.T(n) = T() + What is the value of recurrence?please explain in detail
User Avatar
0 votes
1 answer
1994
dynamic programming
User Avatar
7 votes
3 answers
1997
Self-doubt
Which of the following is exact recurrence relation for binary search (in terms of number of comparisons) ? 1. T(n) = 2T(n/2) + 1 2. T(n) = 2T(n/2) + 2 Please specify relevant reasons.
Which of the following is exact recurrence relation for binary search (in terms of number of comparisons) ?1. T(n) = 2T(n/2) + 12. T(n) = 2T(n/2) + 2Please specify releva...
User Avatar
3 votes
3 answers
1998
Sorted List
suppose there are 4 sorted lists of n/4 elements each. if we merge these list into a single sorted list of n elements, for the n=400 number of key comparisons in the worst case using an efficient algorithm is
suppose there are 4 sorted lists of n/4 elements each. if we merge these list into a single sorted list of n elements, for the n=400 number of key comparisons in the wors...
User Avatar
0 votes
3 answers
1999
Solve this Q
Q. Consider the following functions. f (n) = 3 n + 100, n > 0 g (n) = n + log n, n > 0 Which of the following is correct for larger values of n? 1.f(n) = Ω(g(n)) and f(n) ≠ O (g(n)) 2. g(n) = O(f(n)) and f(n) ≠ Ω (g(n)) 3. f(n) = θ(g(n)) 4.None of these
Q. Consider the following functions.f (n) = 3 n + 100, n 0g (n) = n + log n, n 0Which of the following is correct for larger values of n?1.f(n) = Ω(g(n)) and f(n) ≠ ...
User Avatar
0 votes
1 answer
2000
DFS back edge
If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge. True or false ?
If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge. True or false ?
User Avatar
1 votes
1 answer
2001
Please solve this Q
Q. The best case of quick sort helps Aditya to sort a particular data set of size ‘n’ in 640 ms. Suresh also tried the same algorithm on similar data set and it took him 256 ms in best case to sort a file of size 16. What could be Aditya’s file size?
Q. The best case of quick sort helps Aditya to sort a particular data set of size ‘n’ in 640 ms. Suresh also tried the same algorithm on similar data set and it took...
User Avatar
0 votes
1 answer
2002
Please solve this Q
What is the time complexity to construct a binary tree when inorder and preorder traversal of the tree is given? 1. O(n) 2.O(n log n) 3. O(n2) 4.O(n2 log n)
What is the time complexity to construct a binary tree when inorder and preorder traversal of the tree is given?1. O(n)2.O(n log n)3. O(n2)4.O(n2 log n)
User Avatar
3 votes
1 answer
2004
Time Complexity
Is the answer D ?
Is the answer D ?
User Avatar
2 votes
2 answers
2005
Optimal Merge Pattern,similar to http://gateoverflow.in/1997/gate2014-2-38
To merge 2 files of size m and n it takes m + n time What will be the optimal time Complexity to merge the files of size 10, 15, 40, 70, 75 and 80?
To merge 2 files of size m and n it takes m + n time What will be the optimal time Complexity to merge the files of size 10, 15, 40, 70, 75 and 80?
User Avatar
2 votes
1 answer
2006
Coreman: Time Complexity
Can you please solve this following question further? What will be the time complexity?
Can you please solve this following question further?What will be the time complexity?
User Avatar
0 votes
0 answers
2007
Algorithm
User Avatar
2 votes
1 answer
2009
master theorem
explain complexity for this
explain complexity for this
User Avatar
1 votes
1 answer
2010
master theorem
is the time complexity for this fuction is O(n)?
is the time complexity for this fuction is O(n)?
User Avatar
Page: