All Questions
Tagged with master-theorem data-structures
8 questions
2
votes
1
answer
100
views
How to find the time comlexity when comparing sublists?
def check_lists(list_1, list_2):
if list_1 == None:
return None
if list_2 == None:
return None
comparison_result = True
for i in range(len(list_1)):
if ...
- 37
0
votes
0
answers
306
views
Can T(n) = 2T(n/4)+ n^3 + n^2 be solved using Master Theorem?
Can the following recursion:
T(n) = 2T(n/4)+ n^3 + n^2
be solved using Master Theorem?
It meets the preconditions that f(n) is positive, a>=1, b>1, and the difference between (n^3 + n^2) and n/...
- 41
0
votes
1
answer
129
views
How to use master method or recursion problem in case of f(n)=n factorial
How to solve T(n) =2T(n/2)+n! using master method or recursion.
- 11
0
votes
2
answers
361
views
How to tell whether a recurrence equation belongs to case one or two of the master theorem
If O(f(x)) is always also Theta(f(x)) as theta is O and omega at the same time. How to tell whether a recurrence equation fits case 1 or case 2 of the master theorem.
For example, 𝑇(𝑛)=4𝑇(𝑛/2)+𝑛²...
- 172
-1
votes
1
answer
418
views
Solve using either master theorem or by expansion
I have two questions, which I have trying but unable to figure them out.
1) 𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑛^4
2) 𝑇(𝑛) = 2𝑇 (𝑛/2) + 𝑛 lg 𝑛
For first one, I am assuming substitution (am I correct?), and ...
0
votes
1
answer
287
views
can t(n)=2t(n/2)+n^0.5/logn can be solved using masters theorem?
I have an argue with my friend ,we had an exam yesterday .I said it couldnt,he said it would be case 1 .Probably he is right,but I cant seem to understand why.
Thanks in advance.
- 53
-2
votes
1
answer
169
views
Solve Recurrence Relation by Master theorem? [closed]
Can someone please clarify this solution a little more?
T(n) = 2T(n^1/2) + log n
Solution:
Let k = log n,
T(n) = T(2^k)=2T(2^(k/2)) + k
Substituting into this the equation S(k) = T(2^k)
we get ...
- 709
3
votes
1
answer
313
views
Master theorem - second case issue
Given the following recursive equations:
T(n) = 5T(n/5)+(5sin^5(5n^5)+5)*n
T(n) = T(n/4)+2sin^2(n^4)
I can easily see that both equations fit the 2nd case of the master theorem,
but due to the fact ...
- 2,355