Big O: find ##c## and ##n_0## if ##g(n)## is known

  • C#
  • Thread starter Korisnik
  • Start date
In summary, the conversation discusses whether it is possible to find constants ##c## and ##n_0## for any function ##f##, given that we know ##g##, by adding up the factors multiplying each term in the equation. The technique works for some functions, but not all. In order for it to work, an appropriate value for ##n_0## must be chosen, so that the other terms have the appropriate asymptotic inequalities.
  • #1
Korisnik
62
1
TL;DR Summary
easy way to find c and n0 if g(n) known in O(g(n))
Is it guaranteed that when I have any kind of function ##f##, that I'll be able to find constants ##c## and ##n_0## if I know ##g## by simply adding up the factors multiplying all the terms in the equation?

Suppose ##f(n) = a\cdot n^{143} + b \cdot n! + d \cdot (n!)! + m \cdot 2^n - p \cdot \sqrt{n} + 42##, now I know here that ##f## is ##\mathcal{O}((n!)!)##, meaning that ##g(n) = (n!)!## (where ##\mathcal{O}## takes ##g(n)##).

But can I immediately assume that that holds if I pick ##c = a + b + d + m + p + 42## (taking absolute values of all the factors multiplying each term in ##f(n)##) and letting ##n_0 = 1## such that ## 0 \leq f(n) \leq c \cdot g(n), \ \forall n\in\mathbb{Z}^+,\ n\geq n_0##?

Will this technique work for all functions ##f##? Moreover, I think this can be simplified further by not even taking the factors before negative terms (in this case ##p##).

Thanks in advance.

Edit:

Actually, I think this is sort of trivial to prove, because if indeed we have the "biggest" function ##g(n)## figured out, then if we simply do the following: $$0 \leq f(n) = a\cdot n^{143} + b \cdot n! + d \cdot (n!)! + m \cdot 2^n - p \cdot \sqrt{n} + 42 \leq c \cdot g(n) = (a + b + d + m + p + 42) \cdot (n!)! = a \cdot (n!)! + b \cdot (n!)! + d \cdot (n!)! + m \cdot (n!)! + p \cdot (n!)! + 42 \cdot (n!)!$$ and each of these new terms grows faster than each of the terms in ##f(n)##, and further, since negative terms only "discontribute", there's no need to even include those, because by excluding them, you get a faster growing function than ##f(n)##.
 
Technology news on Phys.org
  • #2
With n0=1 this won't work.

Consider f(x)=x!+2x. Your approach would lead to g(x)=2x!, then g(1)=2 but f(1)=3.

The approach works if you choose an n0 such that the other terms have the asymptotic inequalities, in this case ##x! \geq 2^x##.
 

FAQ: Big O: find ##c## and ##n_0## if ##g(n)## is known

1. What is "Big O" notation?

Big O notation is a mathematical notation used to describe the limiting behavior of a function when the input size approaches infinity. It is commonly used in computer science to analyze the efficiency and complexity of algorithms.

2. What does it mean to "find ##c## and ##n_0##" in Big O?

When using Big O notation, it is common to express the efficiency of an algorithm as a function of the input size, denoted as ##n##. To find ##c## and ##n_0##, we are trying to determine the values of these constants in the equation ##g(n) = c \cdot f(n)##, where ##f(n)## represents the algorithm's efficiency and ##g(n)## represents the input size.

3. How is ##g(n)## related to ##c## and ##n_0## in Big O?

In Big O notation, ##g(n)## is used to represent the upper bound of the algorithm's efficiency. This means that ##g(n)## will always be less than or equal to the actual efficiency, denoted by ##f(n)##. ##c## and ##n_0## are used to determine the specific upper bound, with ##c## representing the maximum efficiency and ##n_0## representing the input size at which the algorithm's efficiency becomes less than or equal to ##c##.

4. How do you find ##c## and ##n_0## for a given algorithm?

To find ##c## and ##n_0## for a given algorithm, one must analyze the algorithm's code and determine its efficiency in terms of the input size, ##n##. This can be done by counting the number of operations performed in the worst case scenario. From there, one can use mathematical techniques such as limits and algebra to solve for ##c## and ##n_0##.

5. Why is it important to find ##c## and ##n_0## in Big O?

Finding ##c## and ##n_0## in Big O allows us to accurately analyze the efficiency and complexity of an algorithm. This information can be used to compare different algorithms and choose the most efficient one for a given task. It also helps in predicting the behavior of an algorithm for larger input sizes, allowing for better optimization and scalability of computer programs.

Similar threads

Replies
8
Views
2K
Replies
15
Views
3K
Replies
1
Views
1K
Replies
5
Views
1K
Replies
7
Views
2K
Replies
1
Views
822
Back
Top