1
$\begingroup$

I searched for this notations (O-, Θ, Ω-) but i don't know their job exactly, I just found their mean in greek language but i don't know what it's mean in math.

I'm was reading about algorithms and their analysis, and author said that algorithms required knowledge of combinatorics, recurrence relations, functions, and above symbols.

So i was asking about their mean in that circle algorithms

$\endgroup$
4
  • $\begingroup$ In what context? I would guess you are probably referring to Big-O, Big-Theta, and Big-Omega notation. $\endgroup$ Oct 29, 2017 at 20:48
  • $\begingroup$ Look for "Big-O notation" or "Landau symbols". $\endgroup$
    – Zubzub
    Oct 29, 2017 at 20:49
  • $\begingroup$ I updated the question, is that clear now ? $\endgroup$
    – user483856
    Oct 29, 2017 at 20:52
  • 1
    $\begingroup$ As @Zubzub noted, look up Big O notation. I've just given the link. Further, the $\Theta$ and $\Omega$ notations are also explained under related asymptotic notations. $\endgroup$
    – Eff
    Oct 29, 2017 at 20:54

1 Answer 1

0
$\begingroup$

In the field of computational complexity, the main object of study is problems and their ability to be 'solved' by algorithms. For example, if I ask you to "Do a series of multiplications", this may be a problem slightly different from the problem where you "Find a series of truth values which satisfies a set of logical formulas" (I'm thinking of 3-SAT here, for those who know what that is) in the sense that the first one might be easier than the second.

This difference in how "hard" problems are to solve is usually defined as how "fast" the fastest algorithm is which solves that problem. For example, in the problem where you "Sort a list", you could go through and find the minimum element and move it to the front, and then do so for each sub-list that remains; BUT, there are smarter algorithms to use.

However, there exist problems that we don't yet have "fast" algorithms to, but for which we can't prove that those "fast" algorithms don't exist. This, roughly, relates to the P vs. NP Problem.

Now, we've been talking about "algorithms" a lot, and how "fast" they are. This "fastness" is what is being referred to by the $\Omega, \Theta, O$ notations. The $\Omega$ notation generally is used to refer to how "fast" an algorithm can possibly run, or equivalently how low the running-time will be, and the $O$ notation is used to refer to the "slowest" that an algorithm will run, or equivalently how high the running-time can be. $\Theta$ is a more precise notation that involves both $\Omega$ and $O$.

For example, if we take a general sorting problem and analyse the Quicksort method of sorting, we can see that the fastest it might run is $n \log (n)$ where the list is $n$ components long, loosely speaking; this is described as $\Omega (n \log (n))$. Similarly, the slowest this algorithm will run is $n^2$ and so the time it will take to run is upper bound by this function, denoted by $O(n^2)$. Here is a cheat sheet with a lot of other algorithms for sorting and their lower and upper bounds on runtimes.

The little mantra I like to keep in my mind when I think of these is that "$O$ is too slow, $\Omega$ is too fast, but $\Theta$ is juuuuuust right!", in a way similar to Goldilocks and the Three Bears!

If this doesn't completely make sense, that is OK! :) This is something which takes many people a lot of work to understand; I've tried to add links in the explanation above so that you have access to other explanations if you wish to go on to gain a better understanding of the materials :D

$\endgroup$

You must log in to answer this question.