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 753 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Prashant. commented Nov 8, 2016 i edited by Prashant. Nov 8, 2016 reply Follow Share ......... 0 votes 0 votes Sushant Gokhale commented Nov 8, 2016 reply Follow Share No, its theta(1)......try again :) 0 votes 0 votes Prashant. commented Nov 8, 2016 i edited by Prashant. Nov 8, 2016 reply Follow Share .................. 0 votes 0 votes Shivam Chauhan commented Nov 8, 2016 reply Follow Share Yes Theta(1). Sine series 0 votes 0 votes Sushant Gokhale commented Nov 8, 2016 reply Follow Share Thats not the reason. Consider what hapens when 'n' goes above 180 degrees. The sin(n) values will start cancelling out each other. Hence, the max value of the above recurrance can be : sin(0) + sin(1) + sin(2).........+ sin(180). This can be evaluated in constant time. So, theta(1) 1 votes 1 votes vijaycs commented Nov 8, 2016 reply Follow Share I think ans should be option A - T(n) = T(n-1) + O(1). So, T(n) = theta(n). Output of this recursion will be theta(1), But anyhow we will have to run this recursion for n times. I know here this function is periodic here but we don't know how this recursive function is written exactly. I mean how n has been modified. Or what are terminating conditions. All we know is, its kind of T(n) = T(n-1) + O(1). 2 votes 2 votes Sushant Gokhale commented Nov 8, 2016 reply Follow Share @Vijay. You are correct if we strictly stick to the method. But using optimization, we can reduce it, right? We are intrested in solution, not the method, right? 1 votes 1 votes mcjoshi commented Nov 9, 2016 reply Follow Share @vijaycs, Yes $\theta(n)$ is correct. 2 votes 2 votes 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.