edited by
383 views
0 votes
0 votes

What is the time complexibilty of the following code?Assume "statement" takes O(1) time.

int x=0;
int A(n)
    {
    statement;
    if (n==1)
        {
        return 1;
        }
    else
        { x  += 4 A(n/2) + n2;
        return x;
        }
    }
edited by

1 Answer

Best answer
5 votes
5 votes
Computing $n^2$ is an $ O(1)$ task and multiplying by $4$ is again an $O(1)$ work.

So recurrence would be $T(n) = T(n/2) + 1$, similar to binary search.

$T(n) =O( logn)$
selected by

Related questions

0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
3
NeelParekh asked Jul 27, 2023
263 views
If an array is split in the form of increasing and decreasing order then what is TC to find minimum element in the array?
2 votes
2 votes
1 answer
4
h4kr asked Dec 30, 2022
432 views
What is the correct time complexity in $\theta()$ ?