Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged time-complexity
1
votes
0
answers
1411
Time complexity
Why [logn]! is not polynomial bounded where [loglogn]! is polynomial bounded? Note [ ] is greatest integer function
Why [logn]! is not polynomial bounded where [loglogn]! is polynomial bounded? Note [ ] is greatest integer function
saurav04
242
views
saurav04
asked
Dec 20, 2015
Algorithms
time-complexity
+
–
0
votes
1
answer
1412
Find the order of val(j)
Q1 ) j = $\frac{n}{2}$ + $\frac{n}{4}$ + $\frac{n}{8}$ + ....... + 1 = O ( ?? ) Q 2 ) j = 1 + $\frac{1}{2}$ + $\frac{1}{3}$ + $\frac{1}{4}$ +..... = O ( ?? ) Q3 ) while ( i=n >0) { j=i/2 i-- } Q4) While (i=0 <= n) { j=i*2 i++ } Q5 while ( i=n >0) { j=j+i i=i/2 }
Q1 ) j = $\frac{n}{2}$ + $\frac{n}{4}$ + $\frac{n}{8}$ + ....... + 1 = O ( ?? )Q 2 ) j = 1 + $\frac{1}{2}$ + $\frac{1}{3}$ + $\frac{1}{4}$ +..... = O ( ?? )Q3 )while ...
pC
497
views
pC
asked
Dec 20, 2015
Algorithms
time-complexity
algorithms
+
–
0
votes
2
answers
1413
finding pair of an element in the array such that diff will be given no.
venky.victory35
685
views
venky.victory35
asked
Dec 19, 2015
Algorithms
algorithms
time-complexity
dynamic-programming
divide-and-conquer
test-series
+
–
0
votes
0
answers
1414
What is the order
a) Order of finding k th Root ( express in terms of k and n where k represent 3 for cube root , n represent size of input )
a) Order of finding k th Root ( express in terms of k and n where k represent 3 for cube root , n represent size of input )
pC
243
views
pC
asked
Dec 19, 2015
Algorithms
algorithms
time-complexity
+
–
0
votes
1
answer
1415
Time Complexity
T(n) = 16T(n/4) + n! i got its ans as logn* n! is it correct ?
T(n) = 16T(n/4) + n!i got its ans as logn* n!is it correct ?
tiger
368
views
tiger
asked
Dec 17, 2015
Algorithms
algorithms
time-complexity
recurrence-relation
+
–
3
votes
3
answers
1416
median of two sorted Arrays
Himanshu1
1.6k
views
Himanshu1
asked
Dec 16, 2015
Algorithms
algorithms
time-complexity
sorting
test-series
+
–
2
votes
1
answer
1417
merge sort
merge sort algo takes 30sec for input size of 64 in worst case, then max input size solvabe in 6 minutes? 512 64 1024 2048
merge sort algo takes 30sec for input size of 64 in worst case, then max input size solvabe in 6 minutes?512 64 1024 2048
gate_forum
1.4k
views
gate_forum
asked
Dec 13, 2015
Algorithms
merge-sort
time-complexity
+
–
0
votes
0
answers
1418
what is difference between following recurrence question
Please explain the difference between the following question or are they same..?? Q1. Find complexity of the recurrence given by T(n)=2*T(n-1)-1 if n>0 1 otherwise Q2. Find complexity of algorithm given by.. T(n)=T ... and in second it means to directly solve the recursion, then how could a running time recurrence have a negative term...??
Please explain the difference between the following question or are they same..??Q1. Find complexity of the recurrence given byT(n)=2*T(n-1)-1 if n>0 1 otherwiseQ...
Abhishekcs10
286
views
Abhishekcs10
asked
Dec 12, 2015
Algorithms
time-complexity
recurrence-relation
+
–
1
votes
0
answers
1419
Fill the Complexity Table From Greedy Strategy
Problem Solution Space Complexity Space Job Sequencing with deadline 2n n2 n Knapsack - Binary 2n Knapsack - Real infinty Optimal Merge Pattern n ! n2 (linear list) n logn (Non-Linear) Prims Algorithm nn n2 (conventional) n+e log n (heap) Kruskal e log n Dijikstra n2 Bellman-Ford ne
ProblemSolution SpaceComplexitySpace Job Sequencing with deadline2nn2nKnapsack - Binary2n Knapsack - Realinfinty Optimal Merge Pattern n !n2 (linear list)n logn (Non-Li...
pC
762
views
pC
asked
Dec 12, 2015
Algorithms
time-complexity
algorithms
+
–
0
votes
0
answers
1420
Fill the complexity table and correct mistakes if any
name best avg worst space work soace Min max 1 3n/2-1 3n/2-1 c + n + log n log n Matrix multiplication N3 N3 N3 Merge Sort ( Top Down ) n log n n log n n log n c+ n + n + logn n+ log n Merge Sort ( Bottom Up ) n log n n log ... k (2k-1) quicksort n log n n log n n2 logn Binary Search 1 log n log n ( complete tree ) n ( skewed Tree) n+ logn log n
namebestavgworstspacework soaceMin max13n/2-13n/2-1c + n + log nlog nMatrix multiplicationN3N3N3Merge Sort ( Top Down )n log n n log nn log nc+ n + n + lognn+ log nMerge ...
pC
334
views
pC
asked
Dec 12, 2015
Algorithms
time-complexity
algorithms
+
–
1
votes
2
answers
1421
Infix expression evaluation complexity
What is the complexity of evaluating an infix expression having n operators?
What is the complexity of evaluating an infix expression having n operators?
bahirNaik
2.8k
views
bahirNaik
asked
Dec 11, 2015
Programming in C
stack
algorithms
time-complexity
+
–
3
votes
2
answers
1422
Time complexity
Consider the code j = n ; while (j >= 1){ for (i = 1 to j ) x = x + 1 ; j = n/2 ; } What is the time complexity? O(nlogn) O(n logn) O(n ) None of the above
Consider the code j = n ;while (j >= 1){ for (i = 1 to j ) x = x + 1 ; j = n/2 ; }What is the time complexity?O(nlogn)O(n logn)O(n )None of the above
ManojK
750
views
ManojK
asked
Dec 8, 2015
Algorithms
time-complexity
+
–
17
votes
2
answers
1423
TIFR CSE 2015 | Part B | Question: 3
Consider the following code fragment in the $C$ programming language when run on a non-negative integer $n$. int f (int n) { if (n==0 || n==1) return 1; else return f (n - 1) + f(n - 2); } Assuming a typical implementation ... $n$. This algorithm runs in polynomial time in $n$ and the optimal running time is polynomial in $n$. The algorithm does not terminate.
Consider the following code fragment in the $C$ programming language when run on a non-negative integer $n$.int f (int n) { if (n==0 || n==1) return 1; else return f (n -...
makhdoom ghaya
1.8k
views
makhdoom ghaya
asked
Dec 7, 2015
Algorithms
tifr2015
algorithms
identify-function
time-complexity
+
–
1
votes
1
answer
1424
time complexity
1. n > (log n)log n 2. 2n > n√n 3. 2n > nlog n explain plz
1. n (log n)log n2. 2n n√n3. 2n nlog nexplain plz
Jay Singh
318
views
Jay Singh
asked
Dec 6, 2015
Algorithms
time-complexity
+
–
22
votes
3
answers
1425
TIFR CSE 2015 | Part B | Question: 1
Consider the following recurrence relation: $T(n) = \begin{cases} 2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$ Which of the following statements is TRUE? $T(n)$ is $O(\log n)$. $T(n)$ ... but not $O(\log^{3/2} n)$. $T(n)$ is $O(\log^{2} n \cdot \log \log n)$ but not $O(\log^{2} n)$.
Consider the following recurrence relation:$T(n)= \begin{cases}2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$Which of the...
makhdoom ghaya
3.0k
views
makhdoom ghaya
asked
Dec 5, 2015
Algorithms
tifr2015
algorithms
recurrence-relation
time-complexity
+
–
2
votes
2
answers
1426
what is the time complexity
priyavssut
408
views
priyavssut
asked
Dec 5, 2015
Algorithms
algorithms
time-complexity
made-easy-test-series
+
–
2
votes
1
answer
1427
MadeEasy Test Series: Algorithms - Time Complexity
Q.19 Consider the following function. What is the worst case running time of the function f for any positive value of n? O(1) O(n) O(n2) O(n3)
Q.19Consider the following function.What is the worst case running time of the function f for any positive value of n?O(1)O(n)O(n2)O(n3)
Akash Kanase
490
views
Akash Kanase
asked
Dec 4, 2015
Algorithms
algorithms
time-complexity
made-easy-test-series
+
–
1
votes
1
answer
1428
Finding complexity in case ratio of two compexity is constant.
Given two positive functions f(n) and g(n). If $\frac{f(n)}{g(n)}=c$, for some constant c ≥ 0 and c is non-negative but not infinite then which of the following is correct? f(n) = O(g(n)) f(n) = θ (g(n)) ... are of same order. In that case they are both upper & lower bounds of each other ! Q 47 From Made Easy FLT 6-Practice Test 14
Given two positive functions f(n) and g(n). If $\frac{f(n)}{g(n)}=c$, for some constant c ≥ 0 and c is non-negative but not infinite then which of the following is corr...
Akash Kanase
670
views
Akash Kanase
asked
Dec 1, 2015
Algorithms
algorithms
time-complexity
made-easy-test-series
+
–
2
votes
3
answers
1429
Find complexity of T(n)=64T(n/8)-n^2lgn
Which is right method to apply for this substitute or recursion... Can we convert it in master theorem format
Which is right method to apply for this substitute or recursion...Can we convert it in master theorem format
sabir
13.3k
views
sabir
asked
Nov 26, 2015
Algorithms
time-complexity
recursion
master-theorem
+
–
1
votes
1
answer
1430
running time of NFA to DFA
running time of NFA to DFA conversion including the case where NFA has $\epsilon$-transition is ?
running time of NFA to DFA conversion including the case where NFA has $\epsilon$-transition is ?
monali
3.2k
views
monali
asked
Nov 24, 2015
Theory of Computation
theory-of-computation
time-complexity
+
–
7
votes
2
answers
1431
Asymptotic notations
The increasing order of following functions in terms of asymptotic complexity is: $\large \\ f_1(n)= n^{0.999999} \log n \qquad // \log n \text{ is not power of } n\\ f_2(n)=10000000*n \\ f_3(n)=10000000^n\\ f_4(n)=n^2$ (a) f1(n); f4(n); f2(n); f3(n) (b) f1(n); f2(n); f3(n); f4(n) (c) f2(n); f1(n); f4(n); f3(n) (d) f1(n); f2(n); f4(n); f3(n)
The increasing order of following functions in terms of asymptotic complexity is:$\large \\ f_1(n)= n^{0.999999} \log n \qquad // \log n \text{ is not power of } n\\ f_2(...
Registered user 1
7.6k
views
Registered user 1
asked
Nov 24, 2015
Algorithms
algorithms
time-complexity
+
–
1
votes
2
answers
1432
time complexity
$\sum\limits_{i=0}^n i^{3} = X$ and following choices for X 1.$\Theta(n^4)$ 2.$\Theta(n^5)$ 3. $O(n^5)$ 4.$\Omega(n^3)$ possible values of $X$
$\sum\limits_{i=0}^n i^{3} = X$and following choices for X1.$\Theta(n^4)$2.$\Theta(n^5)$3. $O(n^5)$4.$\Omega(n^3)$possible values of $X$
tiger
561
views
tiger
asked
Nov 24, 2015
Algorithms
algorithms
time-complexity
multiple-selects
+
–
1
votes
1
answer
1433
Recurrence
How to build Recurrence relation for Time complexity double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += foo(i); } return sum; } }
How to build Recurrence relation for Time complexity double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += f...
tiger
556
views
tiger
asked
Nov 24, 2015
Algorithms
recurrence-relation
time-complexity
+
–
2
votes
3
answers
1434
Sorting
A machine took 200 sec to sort 200 names,using bubble sort.In 800 sec,it can approximately sort ? a. 400 names b. 800 names c. 750 names d. 850 names
A machine took 200 sec to sort 200 names,using bubble sort.In 800 sec,it can approximately sort ?a. 400 names b. 800 names c. 750 names d. 850 names
Soumyashree
4.7k
views
Soumyashree
asked
Nov 21, 2015
Algorithms
sorting
time-complexity
+
–
1
votes
1
answer
1435
Algorithm
When s be a sorted array of n integers , and t(n) s the time taken for the most efficient algorithm to determine if there are 2 elements with sum less than 1000 in s, then which of the following statements is true? t(n) is O(1) n<=t(n)<= n logn n logn<= t(n) <(n/2) t(n) =(n/2)
When s be a sorted array of n integers , and t(n) s the time taken for the most efficient algorithm to determine if there are 2 elements with sum less than 1000 in s, the...
Soumyashree
340
views
Soumyashree
asked
Nov 21, 2015
Algorithms
algorithms
sorting
time-complexity
+
–
1
votes
1
answer
1436
Calculate the time complexity
Let f(n) = Ω(n), g(n) = O(n) and h(n) = θ(n). Then [f(n) ⋅ g(n)] + h(n) is _______.
Let f(n) = Ω(n), g(n) = O(n) and h(n) = θ(n). Then [f(n) ⋅ g(n)] + h(n) is _______.
Sonam
549
views
Sonam
asked
Nov 20, 2015
Algorithms
time-complexity
asymptotic-notation
+
–
19
votes
5
answers
1437
TIFR CSE 2014 | Part B | Question: 7
Which of the following statements is TRUE for all sufficiently large $n$? $\displaystyle \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}} < n^{1/4}$ $\displaystyle 2^{\sqrt{\log n}} < n^{1/4} < \left(\log n\right)^{\log\log n}$ ... $\displaystyle 2^{\sqrt{\log n}} < \left(\log n\right)^{\log\log n} < n^{1/4}$
Which of the following statements is TRUE for all sufficiently large $n$?$\displaystyle \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}} < n^{1/4}$ $\displaystyle 2^{...
makhdoom ghaya
3.9k
views
makhdoom ghaya
asked
Nov 19, 2015
Algorithms
tifr2014
algorithms
time-complexity
+
–
0
votes
2
answers
1438
Maximum depth of recursion tree
Given answer: C Please explain
Given answer: CPlease explain
shikharV
491
views
shikharV
asked
Nov 18, 2015
Algorithms
algorithms
time-complexity
test-series
+
–
4
votes
1
answer
1439
Comparing Time complexities
Consider the following functions: $\begin{array}{rcl|rcl} F(n) &=& n^{\,4/3} & G(n) &=& 2^{\large \,2^{\,\LARGE n}}\\[1em] H(n) &=& 2^{\large \,n^{\,\LARGE 2}} & I(n) &=& n!\\[1em] J(n) &=& 2^{\,n} \end{array}$ Which of ... $F(n) < J(n) < I(n) < G(n) < H(n)$ $I(n) = O \Bigl ( H(n) \Bigr )$
Consider the following functions:$$\begin{array}{rcl|rcl}F(n) &=& n^{\,4/3} &G(n) &=& 2^{\large \,2^{\,\LARGE n}}\\[1em]H(n) &=& 2^{\large \,n^{\,\LARGE 2}} &I(n) &=& n!\...
shikharV
1.8k
views
shikharV
asked
Nov 17, 2015
Algorithms
time-complexity
algorithms
+
–
0
votes
3
answers
1440
Finding Time complexity
Given answer: B Please explain
Given answer: BPlease explain
shikharV
2.0k
views
shikharV
asked
Nov 17, 2015
Algorithms
time-complexity
algorithms
recursion
test-series
+
–
Page:
« prev
1
...
43
44
45
46
47
48
49
50
51
52
53
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register