Member Avatar for ncis_sg1

Ok so this is the first time I have ever seen this and it is very confusing. I have an assignment that I need to complete by Sunday night but I am having no luck in this question. Could anyone explain how I am to finish this in a easy to understand way?

Here is the question:

Assume f1(n) is O(g1(n)) and f2(n) is O(g2(n)), show that f1(n)/f2(n) is NOT O(g1(n) / g2(n)).

Of course all the 1's and 2's are supposed to be subscripts but I do not know how to do that on this form. Thank you for any and all help. Also I am to start with the definition of big-O.

  • 2 Contributors
  • 1 Reply
  • 206 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by mike_2000_17
Member Avatar for mike_2000_17

The O() means "of the order of". Generally, a function is of the order of its biggest term, i.e., the term that, as n becomes very big, dominates all the others, in other words, the only term that really matters for large values of n. So, if f1(n) = A*n + B*n^2, then it is of order n^2, so you would say that f1 is O(n^2), i.e., g1(n) = n^2. So, just think of g1 as "the largest term of" f1. If the function is now f3(n) = f1(n) / f2(n), then the corresponding g3(n) should be the largest term of f3(n). The question asks to demonstrate that the largest term of f3 is not going to be g1 / g2, i.e., the largest term of (f1 / f2) is not equal to the largest term of f1 divided by the largest term of f2. It is a rather straight-forward demonstration to make.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.