Register
Webpage for Algorithms

Recent questions tagged algorithms

0 votes
1 answer
1802
MadeEasy Subject Test: Algorithms - Graph Algorithms
complexity of kruskal algorithum for finding the minimum cost spanning tree of an undirected graph contain n vertices and m edges if the edge are already sorted.??
complexity of kruskal algorithum for finding the minimum cost spanning tree of an undirected graph contain n vertices and m edges if the edge are already sorted.??
User Avatar
0 votes
0 answers
1805
madeeasy class notes
https://gateoverflow.in/?qa=blob&qa_blobid=15895383759487537860 find complexity ?? where n is prime. someone plz explain??
https://gateoverflow.in/?qa=blob&qa_blobid=15895383759487537860find complexity ??where n is prime.someone plz explain??
User Avatar
0 votes
0 answers
1806
Doubt in this question
https://gateoverflow.in/8398/gate2015-3-4 here it will be [n (n-1)/2]^2 ie; n^2 (n-1)^2/4 => n^2(n^2 -2n+1^2)/4 => n^4 -2n^3+n^2 for bigh oh consider highest power term therfore O(n^4) also θ(n^4) With this (a) θ(n^4) is valid (d) Ω(n^3) valid But how come option 2 is valid
https://gateoverflow.in/8398/gate2015-3-4here it will be[n (n-1)/2]^2 ie; n^2 (n-1)^2/4= n^2(n^2 -2n+1^2)/4= n^4 -2n^3+n^2for bigh oh consider highest power term therfore...
User Avatar
0 votes
1 answer
1808
The Infiniteness Problem
what is the Infiniteness Problem?
what is the Infiniteness Problem?
User Avatar
2 votes
2 answers
1809
Doubt Algorithms Gate 2003
2^2n =O(2^n) True or False Its false but why
2^2n =O(2^n) True or FalseIts false but why
User Avatar
0 votes
0 answers
1811
Doubt Algorithms
I wanted to know how θ is derived for a problem. Can we write it directly Example n^4 + n^3+ n^2 Here worst case will be n^4 since it is the term with highest power(worst). Similarly can i get θ
I wanted to know how θ is derived for a problem. Can we write it directly Example n^4 + n^3+ n^2 Here worst case will be n^4 since it is the term with highest power(wors...
User Avatar
1 votes
0 answers
1812
linked list
Let P be a single linked list.Let Q be a pointer to an intermediate node 'X' in the list.What is the worst case time complexity of best known algorithm to delete the node 'X ' from the list
Let P be a single linked list.Let Q be a pointer to an intermediate node 'X' in the list.What is the worst case time complexity of best known algorithm to delete the node...
User Avatar
1 votes
1 answer
1813
Algorithms recurrence relation
Base condition T(n) = 1 Otherwise T(n) = T(n-1) +n Then After solving i got to this step ...how should i generalize now T(n) = T( n-k) + n-(k-1) + n-(k-2)+n
Base condition T(n) = 1Otherwise T(n) = T(n-1) +n Then After solving i got to this step ...how should i generalize nowT(n) = T( n-k) + n-(k-1) + n-(k-2)+n
User Avatar
3 votes
1 answer
1814
Previous Year Gate Question Doubt
From CLRS the complexity of radix sort is theta(d(n+k)) where d is # of digits , k is range and n is numbers . So how option C is right . Plz solve it on the basis of mine given complexity .
From CLRS the complexity of radix sort is theta(d(n+k)) where d is # of digits , k is range and n is numbers . So how option C is right . Plz solve it on the basis of min...
User Avatar
1 votes
2 answers
1815
Regarding prims algo
Hello, I have doubt regarding prims algorithm 1)should we choose the lowest cost edge and then implement algo further? 2)Or we choose any vertex and then lowest cost edge of that vertex?
Hello,I have doubt regarding prims algorithm1)should we choose the lowest cost edge and then implement algo further?2)Or we choose any vertex and then lowest cost edge of...
User Avatar
3 votes
0 answers
1816
MadeEasy Subject Test: Algorithms - Time Complexity
https://gateoverflow.in/?qa=blob&qa_blobid=6856287731579574233 someone plz tell ??
https://gateoverflow.in/?qa=blob&qa_blobid=6856287731579574233someone plz tell ??
User Avatar
1 votes
1 answer
1817
Internet
for ( i= 1; i<=n; i++) for(j=n/3: j<=2n; j=j+n/3) sum =sum+1; What will be O and θ for this
for ( i= 1; i<=n; i++) for(j=n/3: j<=2n; j=j+n/3) sum =sum+1;What will be O and θ for this
User Avatar
0 votes
0 answers
1819
Question on Inversion and sorting
The average number of inversions in an unsorted array of n elements is? (Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j) A.) n(n-1)/2 B.) n(n-1)/4 C.) n(n+1)/2 D.) n!/2
The average number of inversions in an unsorted array of n elements is?(Two elements a[i] and a[j] form an inversion if a[i] a[j] and i < j)A.) n(n-1)/2B.) n(n-1)/4C.) n...
User Avatar
2 votes
1 answer
1821
#TestBook
Suppose in an array A[] , we exchange elements A[i] and A[i+k] , which were originally out of order A) at least 1 and at most 2k-1 inversions are removed B) at least 2 and at most 2k inversions are removed C)at least 0 and at most k inversions are removed D) none
Suppose in an array A[] , we exchange elements A[i] and A[i+k] , which were originally out of orderA) at least 1 and at most 2k-1 inversions are removedB) at least 2 and ...
User Avatar
0 votes
1 answer
1822
Time complexity for below Code
i = n; While(i > 0) { i= i/2; }
i = n;While(i 0){ i= i/2;}
User Avatar
2 votes
1 answer
1823
Time Complexity of the following code
for i <--- 1 to n for j <---- 1 to n/2 X = X + 1 (i and j both are incrementing by 1) Outer runs for n times and inner for n/2 So will it be n(n/2) => O(n^2) times...
for i < - 1 to n for j < 1 to n/2 X = X + 1(i and j both are incrementing by 1)Outer runs for n times and inner for n/2 So will it be n(n...
User Avatar
0 votes
0 answers
1824
Master theorem
T(n) = T(n-1) + n In which case it falls ??
T(n) = T(n-1) + nIn which case it falls ??
User Avatar
0 votes
1 answer
1825
Algo Recurrence Relation using Bck Substitution
T(n) = 4T(n/2) + C ......where C Constant T(n) = 16T(n/4) + 5C Cant figure out how to generalize and compare with base condition T(n) = 1 from above step.
T(n) = 4T(n/2) + C ......where C ConstantT(n) = 16T(n/4) + 5CCant figure out how to generalize and compare with base condition T(n) = 1 from above step.
User Avatar
1 votes
0 answers
1826
What will be the Complexity for the recurrence relation
T(n) = 2T(n/2) + log n By substitution T(n) = 4T(n/4) + 2log n/2 + logn I got stucked here
T(n) = 2T(n/2) + log nBy substitution T(n) = 4T(n/4) + 2log n/2 + lognI got stucked here
User Avatar
0 votes
0 answers
1827
time complexity
please explain the answer in detail
please explain the answer in detail
User Avatar
2 votes
1 answer
1828
Search, Insert and Delete in Multiway search Trees
Hi Guys, What is the time complexity of Insert, Search and Delete operation in Multiway Trees (mainly B-tree and B+ Tree) ?
Hi Guys,What is the time complexity of Insert, Search and Delete operation in Multiway Trees (mainly B-tree and B+ Tree) ?
User Avatar
2 votes
3 answers
1829
Sorting
Two unsorted arrays of size m and n are to be sorted into a single array, what is best case time complexity?
Two unsorted arrays of size m and n are to be sorted into a single array, what is best case time complexity?
User Avatar
Page: