CODEWITHSUNDEEP
algorithmbig-o
Qirohchan
Qirohchan

Reputation: 1137

Improving complex

I am having a confusion. If I have to prove,

Now, in this, if I calculate the limit,

By this can I Say that this does belongs to big-o(4n). Be Which is not true for any value of n. Is this the correct way of proving?

Upvotes: 0

Views: 64

Answers (3)

ROMANIA_engineer
ROMANIA_engineer

Reputation: 56694

A constant doesn't influence the O time complexity.

I mean O(2*n) = 2*O(n) = O(n).

If 2n+1 is in O(4n) => 2n+1 is in O(n).

Because lim(n->infinite)(2n+1)/n = 2 is a finite number => 2n+1 is in O(n).

Upvotes: 1

Elisha
Elisha

Reputation: 4951

according to definition, if there is a c constant which hold for f(n) <= c*g(n), then f(n) belongs to g(n). so indeed, (2n+1) belongs to O(4n) because there are the constants 1 and 4 which hold:
1*(2n+1) <= 4n <= 4*(2n+1)

(This is also show that (4n) belongs to O(2n+1). this is because they are both O(n))

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65498

There is no best constant. As you've observed, 2 is not going to work. For every epsilon > 0, however, the constant 2 + epsilon will work. This can be proved in general by expanding the definition of limit. The condition for the limit of f(n)/g(n) to approach c as n goes to infinity is that, for every epsilon > 0, there exists n0 such that, for all n > n0, we have |f(n)/g(n) - c| < epsilon, which implies f(n)/g(n) < c + epsilon, which implies that f(n) < (c + epsilon) g(n). It follows that f(n) is O(g(n)), with big-O constant c + epsilon.

Upvotes: 0

Related Questions