Register

Recent questions tagged time-complexity

2 votes
2 answers
1471
What is the worst case time complexity of this function?
int fun(int n) { int count=0; for (int i= n; i> 0; i/=2) for(int j=0; j< i; j++) count+= 1; return count; }
int fun(int n) { int count=0; for (int i= n; i 0; i/=2) for(int j=0; j< i; j++) count+= 1; return count; }
User Avatar
0 votes
2 answers
1474
A average number of comparison performed by the merge sort algorithm ,In Merging two sorted lists of length 2 is
If I have two lists of length 2 then no of comparisons in the worst case would be 2 only , since If I have say 10,20 in list A and 5,7 in list B so then on merging 10 is ...
User Avatar
1 votes
1 answer
1475
Given n points in the xy plane, what is the time complexity to find the closest pair?
what is the approach of this question , Is it that first we will traverse all the pairs then find the minimum distance between all the pairs
what is the approach of this question , Is it that first we will traverse all the pairs then find the minimum distance between all the pairs
User Avatar
2 votes
2 answers
1477
Find Time complexity
User Avatar
4 votes
2 answers
1478
Time Complexity of a Custom Quick Sort Design
Given an instance of custom quick sort in which the Pivot element is always the $\left( \frac{n}{4} \right)^{th}$ ... is the time complexity of this Custom Quick Sort? A) $\mathcal{O}(n\log{}n)$ B) $\mathcal{O}(n^2)$
Given an instance of custom quick sort in which the Pivot element is always the $\left( \frac{n}{4} \right)^{th}$ smallest element. GIven a large array as input and an im...
User Avatar
1 votes
1 answer
1479
How many recursive calls are made by gcd function ?
I have already gone through the links of stackoverflow on this topic but still couldn't understand it clearly , so please explain the logic behind this .
I have already gone through the links of stackoverflow on this topic but still couldn't understand it clearly , so please explain the logic behind this .
User Avatar
0 votes
1 answer
1480
what is the tightest lower bound of the below pseudo-code ?
int isprime(int n ) { for(int i=2;i<=sqrt(n) ; i++) { if(n%i==0) { not prime } }
int isprime(int n ){for(int i=2;i<=sqrt(n) ; i++){if(n%i==0){not prime}}
User Avatar
0 votes
2 answers
1484
what is the use of reducing a problem for which no polynomial time algorithm exist into some another problem ?
If I have a problem A for which no polynomial time algo exists then what do we achieve by reducing it to another problemB and then proving by contradiction that if we cou...
User Avatar
6 votes
2 answers
1486
Assume that a CPU can process $10^8$ operations per second. Suppose you have to sort an array with $10^6$ elements. Which of the following is true?
Assume that a CPU can process $10^8$ operations per second. Suppose you have to sort an array with $10^6$ elements. Which of the following is true? 1. Insertion sort will...
User Avatar
1 votes
1 answer
1491
Time complexity of a while loop
Assuming n>2 A() { while(n>1) { n = n/2; } }
Assuming n>2 A() { while(n>1) { n = n/2; } }
User Avatar
1 votes
1 answer
1492
doubt
How n + n/2 + n/4 + .... 1 can approximate it as an infinite GP? Is it =1+2+4+8+..........n/4 + n/2 +n ? =O(2^n) ?
How n + n/2 + n/4 + .... 1 can approximate it as an infinite GP?Is it =1+2+4+8+..........n/4 + n/2 +n ?=O(2^n) ?
User Avatar
0 votes
1 answer
1493
doubt
Is it loglog(2^2^2^2)=4 Let n=(2^(2^(2^2)))=2^16 Loglogn=4 T(n)=1+T(2^8)=2+T(2^4)=3+T(2^2)=4+T(2)=5 Let n= (2^(2^(2^(2^(2^2)))))=2^(2^65536) Loglog n = 65536
Is it loglog(2^2^2^2)=4Let n=(2^(2^(2^2)))=2^16Loglogn=4T(n)=1+T(2^8)=2+T(2^4)=3+T(2^2)=4+T(2)=5Let n= (2^(2^(2^(2^(2^2)))))=2^(2^65536)Loglog n = 65536
User Avatar
1 votes
2 answers
1494
What is the time complexity ?
time complexity question Sum=0 for(i=1; i<=n;i++) { for(j=1;j<=i;j++) { if(j%i==0) { for(k=1;k<=n;k++) { sum=sum+k; } } } }
time complexity questionSum=0 for(i=1; i<=n;i++) { for(j=1;j<=i;j++) { if(j%i==0) { for(k=1;k<=n;k++) { sum=sum+k; } } } }
User Avatar
0 votes
2 answers
1497
find the running time of the following nested loop
for(i=1;i<=n;i=i*2); for(j=1;j<=i;j=j+1); { }
for(i=1;i<=n;i=i*2);for(j=1;j<=i;j=j+1);{}
User Avatar
0 votes
1 answer
1499
Time com
Consider a binary tree having 'n' elements or 'n' nodes the tree is organized in such a way that at every level 'i' there are 'i' nodes assuming root to be at level 1 the height or depth of binary tree is O(......)
Consider a binary tree having 'n' elements or 'n' nodes the tree is organized in such a way that at every level 'i' there are 'i' nodes assuming root to be at level 1 the...
User Avatar
0 votes
2 answers
1500
Time complexity
Consider a sorted array of 'n' elements an element in the array is said to be majority element if it is occuring more than n/2 times of the array, the time complexity of algorithm which is most efficient to determine if the array contains majority element or not is O(... )?
Consider a sorted array of 'n' elements an element in the array is said to be majority element if it is occuring more than n/2 times of the array, the time complexity of ...
User Avatar
Page: