0
$\begingroup$

The last times i was searching a lot to understanding Big O notation or in general asymptotic notations concepts because i didnt hear about it or them before starting studying in computer science.

  • (In computer science) Since to get asymptotic notation of a function we must get firstly the function itself. And because functions can be sometimes complex therefore dificult to compare between each other, we find their asymptotic notations. So asymptotic notations are used because we don't want to deal with complex functions, and their purposes is only comparing between two or more algorithm's efficiency for large values of n in a simplest way. Am i right?

  • In math thoes notations can be used for n approaching to some real number a [n-->a] (not only to infinity), but in computer science is used only for large n (n--> approcah to infinity). Am i right?

  • (In computer science) When we have f(n)=O(g(n)) this means that for all n>n0 when we multiply g(n) to some constant c we get f(n) : f(n) = c * g(n). So my question is, this constant c is constant only for given n and will change for every different value of n (case 1), or c constant is constant for all values of n which therefore means that after n0 point f(n) graphic will be parallel to g(n) graphic (case 2)?

I asked this question to myself, my head give me this answer: "If case 1 is true c constant will not be a constant, and it will vary according to n, Else if case 2 is true, why some g(n) functions that is said to be big O of f(n) are not really parallel to f(n)." As you see there is where i was confused.

Improve this question
$\endgroup$
1
  • $\begingroup$ By definition, a constant does not vary ! $\endgroup$ Commented Nov 28, 2022 at 20:28

2 Answers 2

Reset to default
1
$\begingroup$

Asymptotics is indeed a way to compare the performance of algorithms, and to attest whether they are usable in practice. However, asymptotics are not everything: in the big-o notation, the value of the constant matters in many cases. For example:

  • Fibonacci heaps are one of the best way to implement heaps in terms of asymptotic complexity of different operations. However, the leading constant is too big for it to be efficient for input sizes in practice;
  • many sorting algorithms have the same $\mathcal{O}(n\log n)$ complexity, but some of them are faster than others;
  • big integer multiplication use different algorithms depending on the size of integers multiplied: as the size increase, so do the multiplicative constant in the $\mathcal{O}$, but the function is asymptotically smaller.

Note that $\mathcal{O}(g)$ is a set of function, not a function itself, though we often write $f(n) = \mathcal{O}(g(n))$ instead of $f\in \mathcal{O}(g)$ for convenience. In computer science, this asymptotic notation is indeed mainly used for $n$ being an integer, and $n\longrightarrow +\infty$.

Also, $f(n) = \mathcal{O}(g(n))$ does NOT mean that there exists $n_0\geqslant 0$ and $c>0$ such that $n\geqslant n_0 \Rightarrow f(n) = cg(n)$.

The $\mathcal{O}$ notation gives an upper bound, not an equality. Using the same notations, it means that there exists $n_0\geqslant 0$ and $c>0$ such that $n\geqslant n_0 \Rightarrow f(n) \leqslant cg(n)$. Also, $c$ is a constant that does NOT depend on $n$ (otherwise any function would be a $\mathcal{O}$ of any other).

What that means is that the function $g$ is ultimately increasing at least as fast as $f$. That's why function graphs are not necessarily parallel.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you very much @Nathaniel for your answer. What about the first question. Have you any idea to correct me if I have misunderstanding? $\endgroup$ Commented Nov 27, 2022 at 13:18
  • $\begingroup$ @Htam your question was a bit confusing but I tried to answer it the best I could. $\endgroup$ Commented Nov 27, 2022 at 13:35
  • $\begingroup$ Thank you again for doing your best :). I mean the point in which I ask for the purpose of asymptotitc notations $\endgroup$ Commented Nov 27, 2022 at 13:45
  • $\begingroup$ That's what I tried to answer in "Asymptotics is indeed a way to compare the performance of algorithms, and to attest whether they are usable in practice." $\endgroup$ Commented Nov 27, 2022 at 13:49
  • $\begingroup$ Thank you: ) i get it now. Last thing i want to ask, is the fact that some functions are so complex that force us to use asymtotic notations? because before getting notations we have already an exact function that express the time or space complexity of an algorithm? $\endgroup$ Commented Nov 27, 2022 at 13:58
1
$\begingroup$

Asymptotic analysis is used mainly for two reasons

  • because of technical difficulties one can meet when evaluating some functions (for instance, we can't easily evaluate $\sum_{i=1}^n\frac1n$ but we know that it is well approximated by $\log(n)+\gamma$);

  • because when we want to compare functions, we prefer to look at the general trend rather than local details that can make the formulas cumbersome. For instance, $n\log n$ and $\log n!$ have the same asymptotic behavior, and the first form can be easier to handle.

Furthermore, in the case of computer programs, we want to abstract away the performance of a particular machine and we are only interested in running times to an arbitrary factor. (In pure mathematics, it makes more sense to avoid this factor.) This is why the notations $O$, $\Omega$, $\Theta$... have been introduced. They are a tradeoff between accuracy and simplicity.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much @Yves. $\endgroup$ Commented Nov 30, 2022 at 11:01

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.