2 votes 2 votes Find the time complexity of the following recurrance relation: T(n) = T(n - 1) + sin(n) , 'n' is measured in degree(s) Options are: A) $theta$(n) B) $theta$(1) C) $theta$(logn) D) $theta$(n.logn) Algorithms algorithms asymptotic-notation + – Sushant Gokhale asked Nov 8, 2016 retagged Jun 4, 2017 by Arjun Sushant Gokhale 712 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Sushant Gokhale commented Nov 10, 2016 reply Follow Share @Vijay and mcjoshi. Lets say you have a machine that doesnt have its own intelligence. SO, it will take O(n). But, I am asking whats the time complexity of given recurrance? Its like the following problem: COnstruct a BST from a set of numbers. Now, if you start constructing BST directly, it will be O(n2). But you optimize it to O(nlogn) by using sorting first and then construct BST. Then why not use optimization here? 0 votes 0 votes mcjoshi commented Nov 10, 2016 reply Follow Share Question here is about solving recurrence only. so its $\theta(n)$ without any doubt. $\tt T(n) = T(n-1) + f(n)$ means you are recursively calling a function $n-times$, and doing work $f(n)$ in each step. so you cannot do this in better than $\theta(n)$, but if problem was to find best solution for some problem, then we had to worry about optimization. 1 votes 1 votes Sushant Gokhale commented Nov 10, 2016 reply Follow Share @mcjoshi. Got you. Thanks. 1 votes 1 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes Sin(n) will have the range (1,-1). which is Theta(1). T(n) = T(n-1) + O(1). = T(n-2)+2*O(1). ..................T(N) = n*O(1) = Theta(n). .: Option A is correct. sarveswara rao v answered Nov 10, 2016 selected Nov 10, 2016 by Sushant Gokhale sarveswara rao v comment Share Follow See all 0 reply Please log in or register to add a comment.