356 views

1 Answer

1 votes
1 votes

Use Master Theorem with  $ a = 1, b = 2, c = 1, d = 0.$

Since $ a = b^{ d} ,(d=log_{a}b)$

we know that f(n) is   $ O(n^{ d} log n) = O(log n).$

edited by

Related questions

0 votes
0 votes
1 answer
1
admin asked May 9, 2020
1,179 views
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
0 votes
0 votes
1 answer
2
admin asked May 9, 2020
512 views
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
0 votes
0 votes
1 answer
4
admin asked May 9, 2020
538 views
Give a big-O estimate for the function $f$ given below if $f$ is an increasing function.$f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$