What exactly does big notation represent

Question

I m really confused about the differences between big O  big Omega  and big Theta notation    I understand that big O is the upper bound and big Omega is the lower bound  but what exactly does big    theta  represent    I have read that it means tight bound  but what does that mean

User · Answer

First of All Theory  Big O   Upper Limit O n   Theta   Order Function - theta n   Omega   Q-Notation Lower Limit  Q n    Why People Are so Confused  In many Blogs  amp  Books How this Statement is emphasised is Like  quot This is Big O n 3  quot  etc  and people often Confuse like weather O n     theta n     Q n  But What Worth keeping in mind is They Are Just Mathematical Function With Names O  Theta  amp  Omega so they have same General Formula of Polynomial  Let  f n    2n4   100n2   10n   50 then  g n    n4  So g n  is Function which Take function as Input and returns Variable with Biggerst Power   Same f n   amp  g n  for Below all explainations  Big O - Function  Provides Upper Bound  Big O n4    3n4   Because 3n4  gt  2n4 3n4 is value of Big O n4  Just like f x    3x n4 is playing a role of x here so  Replacing n4 with x so  Big O x     2x   Now we both are happy General Concept is So 0   f n    O x   O x     cg n    3n4 Putting Value  0   2n4   100n2   10n   50   3n4 3n4 is our Upper Bound Theta n  Provides Lower Bound Theta n4    cg n    2n4 Because 2n4   Our Example f n  2n4 is Value of Theta n4  so  0   cg n    f n  0   2n4   2n4   100n2   10n   50 2n4 is our Lower Bound Omega n - Order Function This is Calculated to find out that weather lower Bound is similar to Upper bound  Case 1   Upper Bound is Similar to Lower Bound if Upper Bound is Similar to Lower Bound  The Average Case is Similar  Example  2n4   f x    2n4  Then Omega n    2n4  Case 2   if Upper Bound is not Similar to Lower Bound in this case  Omega n  is Not fixed but Omega n  is the set of functions with the same order of growth as g n    Example 2n4   f x    3n4  This is Our Default Case  Then  Omega n    c n4  is a set of functions with 2   c    3  Hope This Explained

User · Answer

First let s understand what big O  big Theta and big Omega are  They are all sets of functions  Big O is giving upper asymptotic bound  while big Omega is giving a lower bound  Big Theta gives both  Everything that is   f n   is also O f n    but not the other way around  T n  is said to be in   f n   if it is both in O f n   and in Omega f n    In sets terminology    f n   is the intersection of O f n   and Omega f n   For example  merge sort worst case is both O n log n   and Omega n log n   - and thus is also   n log n    but it is also O n 2   since n 2 is asymptotically  quot bigger quot  than it  However  it is not   n 2   Since the algorithm is not Omega n 2   A bit deeper mathematic explanation O n  is asymptotic upper bound  If T n  is O f n    it means that from a certain n0  there is a constant C such that T n   lt   C   f n   On the other hand   big-Omega says there is a constant C2 such that T n   gt   C2   f n     Do not confuse  Not to be confused with worst  best and average cases analysis  all three  Omega  O  Theta  notation are not related to the best  worst and average cases analysis of algorithms  Each one of these can be applied to each analysis  We usually use it to analyze complexity of algorithms  like the merge sort example above   When we say  quot Algorithm A is O f n   quot   what we really mean is  quot The algorithms complexity under the worst1 case analysis is O f n   quot  - meaning - it scales  quot similar quot   or formally  not worse than  the function f n   Why we care for the asymptotic bound of an algorithm  Well  there are many reasons for it  but I believe the most important of them are   It is much harder to determine the exact complexity function  thus we  quot compromise quot  on the big-O big-Theta notations  which are informative enough theoretically  The exact number of ops is also platform dependent  For example  if we have a vector  list  of 16 numbers  How much ops will it take  The answer is  it depends  Some CPUs allow vector additions  while other don t  so the answer varies between different implementations and different machines  which is an undesired property  The big-O notation however is much more constant between machines and implementations   To demonstrate this issue  have a look at the following graphs   It is clear that f n    2 n is  quot worse quot  than f n    n  But the difference is not quite as drastic as it is from the other function  We can see that f n  logn quickly getting much lower than the other functions  and f n    n 2 is quickly getting much higher than the others  So - because of the reasons above  we  quot ignore quot  the constant factors  2  in the graphs example   and take only the big-O notation  In the above example  f n  n  f n  2 n will both be in O n  and in Omega n  - and thus will also be in Theta n   On the other hand - f n  logn will be in O n   it is  quot better quot  than f n  n   but will NOT be in Omega n  - and thus will also NOT be in Theta n   Symetrically  f n  n 2 will be in Omega n   but NOT in O n   and thus - is also NOT Theta n    1Usually  though not always  when the analysis class  worst  average and best  is missing  we really mean the worst case

User · Answer

Big Theta notation   Nothing to mess up buddy    If we have a positive valued functions f n  and g n  takes a positive valued argument n then   g n   defined as  f n  there exist constants c1 c2 and n1 for all n  n1   where c1 g n  lt  f n  lt  c2 g n   Let s take an example   let f n      g n    c1 5 and c2 8 and n1 1  Among all the notations    notation gives the best intuition about the rate of growth of function because it gives us a tight bound unlike  big-oh and big -omega which gives the upper and lower bounds respectively     tells us that g n  is as close as f n  rate of growth of g n  is as close to the rate of growth of f n  as possible

User · Answer

Theta n   A function f n  belongs to Theta g n    if there exists positive constants c1 and c2 such that f n  can be sandwiched between c1 g n   and c2 g n    i e it gives both upper and as well as lower bound      Theta g n       f n    there exists positive constants c1 c2 and n1 such that                    0 lt  c1 g n   lt  f n  lt  c2 g n   for all n  n1     when we say f n  c2 g n   or f n  c1 g n   it represents asymptotically tight bound   O n   It gives only upper bound  may or may not be tight      O g n       f n    there exists positive constants c and n1 such that 0 lt  f n  lt  cg n  for all n  n1    ex  The bound 2  n 2    O n 2  is asymptotically tight  whereas the bound 2 n   O n 2  is not asymptotically tight   o n   It gives only upper bound  never a tight bound      the notable difference between O n   amp  o n  is f n  is less than cg n    for all n  n1 but not equal as in O n     ex  2 n   o n 2   but 2  n 2     o n 2

User · Answer

It means that the algorithm is both big-O and big-Omega in the given function     For example  if it is   n   then there is some constant k  such that your function  run-time  whatever   is larger than n k for sufficiently large n  and some other constant K such that your function is smaller than n K for sufficiently large n     In other words  for sufficiently large n  it is sandwiched between two linear functions    For k  lt  K and n sufficiently large  n k  lt  f n   lt  n K

User · Answer

I hope this is what you may want to find in the classical CLRS page 66

[algorithm] What exactly does big ? notation represent?

Why People Are so Confused?

Big O - Function (Provides Upper Bound)

Theta(n) Provides Lower Bound

Omega n - Order Function

Examples related to algorithm

Examples related to computer-science

Examples related to big-o

Examples related to notation

Examples related to big-theta