All Questions
Tagged with recurrence complexity-theory
109 questions
0
votes
1
answer
265
views
How to choose base case for substitution method for solving recurrences?
I tried to find out how to solve recurrences using substitution method, but I don't understand: how is the base case chosen when the base case is not given explicitly?
I have two problems:
T(n) = 2T(...
- 1
0
votes
0
answers
41
views
Time complexity of a divide and conquer algorithm that searches for a value in an n x m table, rows and columns are sorted
I am confused about the time complexity of this algorithm because I am thinking it could be something like T(n) = 3T(n/2) ... but since the array has a size of nxm instead of nxn and I am using ...
- 21
-1
votes
1
answer
29
views
Solving non-linear recurernce relation
I want to solve analytically this relation :
T[n] =1/n * T^2[n/2]+n
We know n is a power of 2.
I know I can't use master theorem.
I tried to replace and replace till I get something.
- 563
-1
votes
1
answer
40
views
Proportional or Constant Complexity?
I have been given a algorithm about The Levenshtein distance between two character strings 𝑎 and 𝑏 is defined as the minimum number of single-character insertions, deletions, or substitutions (so-...
0
votes
1
answer
63
views
Solving a Recurrence relation formula with squared
I Hope someone Can help me with that:
I will be asked to answer what is the runtime complexity of the algorithm.
I tried to set m=2^ and still failed
Thanks
- 27
0
votes
1
answer
935
views
Solve the recurrence relations using the guess and check method
I've got a problem where I forgot how to do recurrence relations and I'm not really sure what the guess and check method is. Does anyone know how to solve them using that method and if so a nice ...
- 17
0
votes
0
answers
65
views
How to compute tight asymptotic bounds for the recurrence
T(n) = 2/3T(n/2) + 3T(n/3) + 8T(n/4)
I tried computing it, but I am confused when there are multiple recurrences.
0
votes
0
answers
1k
views
Complexity of T(n)=16T(n/4)-2n^2
I'm having difficulties solving this recurrence relation: T(n)=16T(n/4)-2n^2. From my understanding I can't use the master theorem because f(n) is only allowed to be positive. Because of that I tried ...
- 35
0
votes
1
answer
696
views
Recurrence relation tree method tight bound
I am trying to find the asymptotic tight bound for this recurrence:
T(n) = T(n/2)+T(2n/4)+n
I am utilizing the recursive tree method to do so, but I am lost towards the end and would appreciate any ...
-2
votes
1
answer
4k
views
What will be complexity of reccurance relation : T (n) = 0.5T (n/2) + 1/n
How to calculate the complexity of this case since master method fails for a<1?
- 27
0
votes
0
answers
431
views
Douglas-Peucker line simplification algorithm time complexity
I am analyzing the time complexity of the Douglas-Peucker line simplification algorithm. Reading online I've found that it has a worst-case running time of O(n^2) where n is the number of points on ...
- 896
2
votes
2
answers
802
views
Recurrence relation: T(n) = T(ceil(n/3)) + T(ceil(3n/5)) + 100*n
I have the recurrence relation as:
T(n) = T(ceil(n/3)) + T(ceil(3n/5)) + 100*n and T(1) = 1
I am trying to solve it using recurrence tree method but I don't know to deal with ceiling function in ...
user15267221
2
votes
0
answers
24
views
Doubts on finding complexity of an algorithm
So far I think I understand the basic of finding algorithm complexity:
Basics operations like read,write,assignments and allocations have constant complexity O(k) that can be simplified as O(1).
For ...
- 469
-1
votes
1
answer
246
views
Recurrence: T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n) , what is the complexity of T(n)?
how to solve the recurrence equation . T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n).
I can solve it if instead of Ω(n), we had (n), but now I can't solve it. please help me!
0
votes
2
answers
38
views
Complexity class of recurrence equation
It's been a while for me since my undergraduate class in algorithms. Could you please help me solving this recurrence equation?
T(0)=14
T(n)=4*T(n/2)+n^2 for n>0
I'm interested in an upper bound ...
- 858