retagged by
712 views
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)
retagged by

1 Answer

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.
selected by
Answer:

Related questions

0 votes
0 votes
2 answers
1
snaily16 asked Jan 9, 2019
561 views
Given below are 4 functions$999999n$$0.99999 n logn$$1.000001^{n}$$n^{2}$The increasing order of the above functions in terms of their asymptotic complexity is?
0 votes
0 votes
0 answers
2
HeadShot asked Nov 30, 2018
221 views
Why not option B as F(n)= O( F(n) ) is trivial ?
0 votes
0 votes
1 answer
4
iamdeepakji asked Aug 31, 2018
1,220 views
What is all asymptotic notation of1. Big-oh2. Big-omega3. theta4. Small-oh5. Small-Omegasuch as theta has reflexive,symmetric and many moreplease write all properties.