[max1]

Hi,

i need advice on how to write this down. I have an alhorithm that runs in

O(1/x - 1/2^x - 1/(x2^x)) time.

is it eays to show that 1/2^x in o(1/x) so i can neglect the second expression but for 1/(x2^x) i have lim_x->x0 x/x2^x = 1 so it is not in o() (right ?) so i cannot neglect it, or can i ? if i can then why?

thnx

[max1]

max1, on 18 August 2014 - 07:46 AM, said:

Hi,

i need advice on how to write this down. I have an alhorithm that runs in

O(1/x - 1/2^x - 1/(x2^x)) time.

is it eays to show that 1/2^x in o(1/x) so i can neglect the second expression but for 1/(x2^x) i have lim_x->x0 x/x2^x = 1 so it is not in o() (right ?) so i cannot neglect it, or can i ? if i can then why?

thnx

I am so sorry for posting this question but seam i don't know my limits....

[macosxnerd101]

Please avoid needlessly bumping your thread.

The same reduction rules apply for little-o as for Big-O. You take the dominant term. Which goes to 0 faster: 1/x or 1/(x2^x)?

Your limit setup is also wrong. You don't go to a specific point, you go out to infinity. That's part of the definition of little-o: for all x > k, for some initial constant k.

So you get: lim_{x \to \infty} (x/x - x/2^{x} - x/(x2^{x})
= lim_{x \to \infty} (1 - x/2^{x} - 1/2^{x}).

I would advise you to look at the ratio test here, as well as L'Hospital's rule.