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; } } Algorithms time-complexity algorithms + – focus _GATE asked Jan 3, 2017 • edited Jan 3, 2017 by srestha focus _GATE 400 views answer comment Share Follow See 1 comment See all 1 1 comment reply Nishant Arora commented Jan 3, 2017 reply Follow Share O(logn) 0 votes 0 votes Please log in or register to add a comment.
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)$ thor answered Jan 3, 2017 • selected Jan 3, 2017 by srestha thor comment Share Follow See all 2 Comments See all 2 2 Comments reply Aghori commented Jan 3, 2017 reply Follow Share Can you please tell me complexity on what basis? Like in sorting we could find complexity on number of comparisons. On what basis you have found here? If it is number of operations then don't you think we should include n² ? 0 votes 0 votes thor commented Jan 3, 2017 reply Follow Share A(n) is a function that calls A(n/2) multiplies it with 4 and adds n^2 and this goes on forming a recurrence relation. 1 votes 1 votes Please log in or register to add a comment.