CODEWITHSUNDEEP
mathrecurrenceasymptotic-complexity
user3339453
user3339453

Reputation: 57

Recurrence relations and asymptotic complexity

I am trying to understand the recurrence relation of f(n) = n^cos n and g(n) = n. I am told that this relation has no asymptotic behavior related to Big O, little o, Big Omega, little omega, or Theta. Something about the oscillations of cos n? Can I receive a little more understanding on this behavior?

When I use L' Hospital rule on my calculator, I get undefined.

Upvotes: 0

Views: 537

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

The function ncos n is O(n). Since -1 ≤ cos n ≤ 1, the function ncos n is always bounded between n-1 and n1, so in particular it's always upper-bounded by O(n). However, it's not Ω(n), because for any number n0 and any constant c, you can find an n > n0 where ncos n < cn. One way to do this is to look for choices of n where cos n is negative; the value of n-ε for any ε > 0 will eventually be smaller than cn for any c.

Hope this helps!

Upvotes: 0

Related Questions