retagged by
1,481 views
5 votes
5 votes
int x=0;
int A(n)
{
    statement //takes O(1) time
    if(n==1) return 1;
    else
    {
        $X+=8.A\left ( \frac{n}{2}\right )+n^3$;
    }
    return X;
}

What is the time complexity f the above code?

retagged by

2 Answers

Best answer
7 votes
7 votes
$\begin{align*} &\text{A(n) is a recursive function having the following recurrence call structure }\\ \\ &\text{x} \leftarrow \text{x} + 8.{\bf\color{red}{\text{A}(n/2)} }+n^3 \\ \\ &\text{Corresponding recurrence relation for time complexity would be} \\ \\ &T(n) = {\bf \large \color{blue}{1}}.{\bf \color{red}{\text{T(n/2)} }}+ O(1) \\ &\Rightarrow O(\log n) \end{align*}$
selected by
0 votes
0 votes

Here we are computing only 'n^3' . It is not any function coll . So it will take constant time.

Related questions

2 votes
2 votes
1 answer
1
0 votes
0 votes
2 answers
2
Shivangi Verma asked Dec 23, 2016
409 views
What is the time complexity to count the number of leaf nodes in a tree? I am getting O(nlogn) but answer is O(n) please anybody explain in detail
0 votes
0 votes
1 answer
3
rajan asked Dec 9, 2016
350 views
how to solve these two using matser thorem.1. t(n)=2t(√n)+n2. t(n)=4t(√n)+(logn)^2
1 votes
1 votes
2 answers
4
vijaycs asked Jul 11, 2016
1,835 views
On which of the following recurrence relation Masters theorem can not be applied ?A. T(n)= 2T(n/2) + n (log n).B. T(n) = T(n/2) + 1.C. T(n) = 8T(n/2) + (log n).D. T(n) = ...