1

For example i have f(N) = 5N +3 from a program. I want to know what is the big (oh) of this function. we say higher order term O(N).

  1. Is this correct method to find big(oh) of any program by dropping lower orders terms and constants?

  2. If we got O(N) by simply looking on that complexity function 5N+3. then, what is the purpose of this formula F(N) <= C* G(N)?

    i got to know that, this formula is just for comparing two functions. my question is,

  3. In this formula, F(N) <= C* G(N), i have F(N) = 5N+3, but what is this upper bound G(N)? Where it comes from? where from will we take it?

i have studied many books, and many posts, but i am still facing confusions.

Community
  • 1
  • 1
Jawwad Rafiq
  • 327
  • 3
  • 20
  • Have you studied Cormen's IOA ? It is explained there. – user2736738 Feb 11 '18 at 10:53
  • Yes i have studied cormen,Steven, Robert, I have six books at home. I have seen many videos from youtube. but i am still confused about it. – Jawwad Rafiq Feb 11 '18 at 10:55
  • 1
    You can check page-47 again. It's so nicely put there. `g(n)` comes from the definition. It says the criteria of saying `f(n)=O(g(n))` only when certain things hold. That is written there. – user2736738 Feb 11 '18 at 11:00
  • The Big (O) notation asymptotically bounds a function from above and below. When we have only an asymptotic upper bound, we use O-notation. For a given function g(n), we denote by O(g.n) (pronounced “big-oh of g of n” or sometimes just “oh of g of n”) the set of functions – Jawwad Rafiq Feb 11 '18 at 11:04
  • 1
    Any `g(n)` that satisfies the conditions will do. For example if `f(n)=5n+3` you can choose `g(n) = 10n` or `g(n)=n/50` or `g(n)=n^2`. For all you can find constants c and n0 such that `f(n) <= c g(n)` for all n > n0. Typically a "simple" function `g(n)` is chosen that works. – Henry Feb 11 '18 at 11:25
  • Its mean, we prove that our F(N) will remain under any G(N) , that is greater than our F(N). mean this function is just for prove. But Another Part: Is this correct method to find big(oh) of any program by dropping lower orders terms and constants? – Jawwad Rafiq Feb 11 '18 at 11:30
  • If the function is a polynomial, yes. But there are also cases like `sqrt(n)+log(n)` where it is not so obvious what to drop. – Henry Feb 11 '18 at 11:37

1 Answers1

1

Q: Is this correct method to find big(oh) of any program by dropping lower orders terms and constants?

Yes, most people who have at least some experience with examining time complexities use this method.

Q: If we got O(N) by simply looking on that complexity function 5N+3. then, what is the purpose of this formula F(N) <= C* G(N)?

To formally prove that you correctly estimated big-oh for certain algorithm. Imagine that you have F(N) = 5N^2 + 10 and (incorrectly) conclude that the big-oh complexity for this example is O(N). By using this formula you can quickly see that this is not true because there does not exist constant C such that for large values of N holds 5N^2 + 10 <= C * N. This would imply C >= 5N + 10/N, but no matter how large constant C you choose, there is always N larger than this constant, so this inequality does not hold.

Q: In this formula, F(N) <= C* G(N), i have F(N) = 5N+3, but what is this upper bound G(N)? Where it comes from? where from will we take it?

It comes from examining F(N), specifically by finding its highest order term. You should have some math knowledge to estimate which function grows faster than the other, for start check this useful link. There are several classes of complexities - constant, logarithmic, polynomial, exponential.. However, in most cases it is easy to find the highest order term for any function. If you are not sure, you can always plot a graph of a function or formally prove that one function grows faster than the other. For example, if F(N) = log(N^3) + sqrt(N) maybe it is not clear at first glance what's the highest order term, but if you calculate or plot log(N^3) for N = 1, 10 and 1000 and sqrt(N) for same values, it is immediately clear that sqrt(N) grows faster, so big-oh for this function is O(sqrt(N)).

Miljen Mikic
  • 14,765
  • 8
  • 58
  • 66
  • "It comes from examining F(N), specifically by finding its highest order term". Its mean, we can take G(N) = N by concluding from F(N). If we get G(N) from F(N), then where do we use these constant, logarithmic, polynomial, exponential.. G(N) functions. I am concluding that: G(N) comes from two things, 1- From F(N), 2- From difference classes of complexities – Jawwad Rafiq Feb 12 '18 at 15:48
  • 1
    @JawwadRafiq Mostly from `F(N)`, complexity classes serve as a helper to quickly compare terms of `F(N)` by rate of growth. If you have e.g. `F(N) = 2^n + n^3` you know from complexity classes that `2^n` belongs to exponential and `n^3` to polynomial and that exponential functions grow faster, which means that big-oh of F(N) is `O(2^n)`. – Miljen Mikic Feb 12 '18 at 16:12