What is the difference between lower bound and tight bound

Question

With the reference of this answer  what is Theta  tight bound    Omega is lower bound  quite understood  the minimum time an algorithm may take  And we know Big-O is for upper bound  means the maximum time an algorithm may take   But I have no idea regarding the Theta

User · Answer

Asymptotic upper bound means that a given algorithm executes during the maximum amount of time  depending on the number of inputs    Let s take a sorting algorithm as an example  If all the elements of an array are in descending order  then to sort them  it will take a running time of O n   showing upper bound complexity  If the array is already sorted  the value will be O 1     Generally  O-notation is used for the upper bound complexity     Asymptotically tight bound  c1g n    x2264  f n    x2264  c2g n   shows the average bound complexity for a function  having a value between bound limits  upper bound and lower  bound   where c1 and c2 are constants

User · Answer

Asymptotic upper bound means that a given algorithm executes during the maximum amount of time  depending on the number of inputs    Let s take a sorting algorithm as an example  If all the elements of an array are in descending order  then to sort them  it will take a running time of O n   showing upper bound complexity  If the array is already sorted  the value will be O 1     Generally  O-notation is used for the upper bound complexity     Asymptotically tight bound  c1g n    x2264  f n    x2264  c2g n   shows the average bound complexity for a function  having a value between bound limits  upper bound and lower  bound   where c1 and c2 are constants

User · Answer

If you have something that s  O f n   that means there s are k  g n  such that f n   le  k g n    If you have something that s   Omega  f n   that means there s are k  g n  such that f n   ge  k g n    And if you have a something with O f n   and  Omega  f n    then it s  Theta  f n    The Wikipedia article is decent  if a little dense

User · Answer

Big O is the upper bound  while Omega is the lower bound  Theta requires both Big O and Omega  so that s why it s referred to as a tight bound  it must be both the upper and lower bound    For example  an algorithm taking Omega n log n  takes at least n log n time  but has no upper limit  An algorithm taking Theta n log n  is far preferential since it takes at least n log n  Omega n log n  and no more than n log n  Big O n log n

User · Answer

Theta -notation  theta notation  is called tight-bound because it s more precise than O-notation and  Omega -notation  omega notation     If I were lazy  I could say that binary search on a sorted array is O n2   O n3   and O 2n   and I would be technically correct in every case   That s because O-notation only specifies an upper bound  and binary search is bounded on the high side by all of those functions  just not very closely  These lazy estimates would be useless    Theta -notation solves this problem by combining O-notation and  Omega -notation  If I say that binary search is  Theta  log n   that gives you more precise information   It tells you that the algorithm is bounded on both sides by the given function  so it will never be significantly faster or slower than stated

User · Answer

Big O is the upper bound  while Omega is the lower bound  Theta requires both Big O and Omega  so that s why it s referred to as a tight bound  it must be both the upper and lower bound    For example  an algorithm taking Omega n log n  takes at least n log n time  but has no upper limit  An algorithm taking Theta n log n  is far preferential since it takes at least n log n  Omega n log n  and no more than n log n  Big O n log n

User · Answer

If I were lazy  I could say that binary search on a sorted array is   O n2   O n3   and O 2n   and I would be technically correct in every   case    We can use o-notation   little-oh   to denote an upper bound that is not asymptotically tight  Both big-oh and little-oh are similar  But  big-oh is likely used to define asymptotically tight upper bound

User · Answer

The basic difference between      Blockquote   asymptotically upper bound and asymptotically tight Asym upperbound means a given algorythm that can executes with maximum amount of time depending upon the number of inputs  for eg in sorting algo if all the array  n elements are in descending order then for ascending them it will take a running time of O n  which shows upper bound complexity  but if they are already sorted then it will take ohm 1  so we generally used  O notation for upper bound complexity   Asym  tightbound bound shows the for eg c1g n  lt  f n  lt  c2g n    shows the tight bound limit such that the function have the value in between two bound  upper bound and lower bound  giving the average case

User · Answer

Precisely the lower bound or   omega   bfon f n  means the set of functions which are asymptotically less or equal to f n  i e U      g n   cf n     for all   un  n   For some c  n    in      Bbb N    And the upper bound or   mathit O   on f n  means the set of functions which are assymptotically greater or equal to f n  which mathematically tells     g n  ge cf n   for all n ge n      for some  c n    in     Bbb N     Now the   Theta   is the intersection of the above written two        theta     Like if a algorithm is like   exactly   Omega left  f n   right     then it s better to say it s   Theta left f n  right       Or   we can say also that it give us the actual speed where    omega   gives us the lowest limit

User · Answer

If you have something that s  O f n   that means there s are k  g n  such that f n   le  k g n    If you have something that s   Omega  f n   that means there s are k  g n  such that f n   ge  k g n    And if you have a something with O f n   and  Omega  f n    then it s  Theta  f n    The Wikipedia article is decent  if a little dense

User · Answer

Precisely the lower bound or   omega   bfon f n  means the set of functions which are asymptotically less or equal to f n  i e U      g n   cf n     for all   un  n   For some c  n    in      Bbb N    And the upper bound or   mathit O   on f n  means the set of functions which are assymptotically greater or equal to f n  which mathematically tells     g n  ge cf n   for all n ge n      for some  c n    in     Bbb N     Now the   Theta   is the intersection of the above written two        theta     Like if a algorithm is like   exactly   Omega left  f n   right     then it s better to say it s   Theta left f n  right       Or   we can say also that it give us the actual speed where    omega   gives us the lowest limit

User · Answer

Big O is the upper bound  while Omega is the lower bound  Theta requires both Big O and Omega  so that s why it s referred to as a tight bound  it must be both the upper and lower bound    For example  an algorithm taking Omega n log n  takes at least n log n time  but has no upper limit  An algorithm taking Theta n log n  is far preferential since it takes at least n log n  Omega n log n  and no more than n log n  Big O n log n

User · Answer

The phrases minimum time and maximum time are a bit misleading here  When we talk about big O notations  it s not the actual time we are interested in  it is how the time increases when our input size gets bigger  And it s usually the average or worst case time we are talking about  not best case  which usually is not meaningful in solving our problems    Using the array search in the accepted answer to the other question as an example  The time it takes to find a particular number in list of size n is n 2   some constant in average  If you treat it as a function f n    n 2 some constant  it increases no faster than g n    n  in the sense as given by Charlie  Also  it increases no slower than g n  either  Hence  g n  is actually both an upper bound and a lower bound of f n  in Big-O notation  so the complexity of linear search is exactly n  meaning that it is Theta n     In this regard  the explanation in the accepted answer to the other question is not entirely correct  which claims that O n  is upper bound because the algorithm can run in constant time for some inputs  this is the best case I mentioned above  which is not really what we want to know about the running time

User · Answer

The phrases minimum time and maximum time are a bit misleading here  When we talk about big O notations  it s not the actual time we are interested in  it is how the time increases when our input size gets bigger  And it s usually the average or worst case time we are talking about  not best case  which usually is not meaningful in solving our problems    Using the array search in the accepted answer to the other question as an example  The time it takes to find a particular number in list of size n is n 2   some constant in average  If you treat it as a function f n    n 2 some constant  it increases no faster than g n    n  in the sense as given by Charlie  Also  it increases no slower than g n  either  Hence  g n  is actually both an upper bound and a lower bound of f n  in Big-O notation  so the complexity of linear search is exactly n  meaning that it is Theta n     In this regard  the explanation in the accepted answer to the other question is not entirely correct  which claims that O n  is upper bound because the algorithm can run in constant time for some inputs  this is the best case I mentioned above  which is not really what we want to know about the running time

User · Answer

If you have something that s  O f n   that means there s are k  g n  such that f n   le  k g n    If you have something that s   Omega  f n   that means there s are k  g n  such that f n   ge  k g n    And if you have a something with O f n   and  Omega  f n    then it s  Theta  f n    The Wikipedia article is decent  if a little dense

User · Answer

Theta -notation  theta notation  is called tight-bound because it s more precise than O-notation and  Omega -notation  omega notation     If I were lazy  I could say that binary search on a sorted array is O n2   O n3   and O 2n   and I would be technically correct in every case   That s because O-notation only specifies an upper bound  and binary search is bounded on the high side by all of those functions  just not very closely  These lazy estimates would be useless    Theta -notation solves this problem by combining O-notation and  Omega -notation  If I say that binary search is  Theta  log n   that gives you more precise information   It tells you that the algorithm is bounded on both sides by the given function  so it will never be significantly faster or slower than stated

User · Answer

The basic difference between      Blockquote   asymptotically upper bound and asymptotically tight Asym upperbound means a given algorythm that can executes with maximum amount of time depending upon the number of inputs  for eg in sorting algo if all the array  n elements are in descending order then for ascending them it will take a running time of O n  which shows upper bound complexity  but if they are already sorted then it will take ohm 1  so we generally used  O notation for upper bound complexity   Asym  tightbound bound shows the for eg c1g n  lt  f n  lt  c2g n    shows the tight bound limit such that the function have the value in between two bound  upper bound and lower bound  giving the average case

User · Answer

If I were lazy  I could say that binary search on a sorted array is   O n2   O n3   and O 2n   and I would be technically correct in every   case    We can use o-notation   little-oh   to denote an upper bound that is not asymptotically tight  Both big-oh and little-oh are similar  But  big-oh is likely used to define asymptotically tight upper bound

User · Answer

If you have something that s  O f n   that means there s are k  g n  such that f n   le  k g n    If you have something that s   Omega  f n   that means there s are k  g n  such that f n   ge  k g n    And if you have a something with O f n   and  Omega  f n    then it s  Theta  f n    The Wikipedia article is decent  if a little dense

User · Answer

Theta -notation  theta notation  is called tight-bound because it s more precise than O-notation and  Omega -notation  omega notation     If I were lazy  I could say that binary search on a sorted array is O n2   O n3   and O 2n   and I would be technically correct in every case   That s because O-notation only specifies an upper bound  and binary search is bounded on the high side by all of those functions  just not very closely  These lazy estimates would be useless    Theta -notation solves this problem by combining O-notation and  Omega -notation  If I say that binary search is  Theta  log n   that gives you more precise information   It tells you that the algorithm is bounded on both sides by the given function  so it will never be significantly faster or slower than stated

User · Answer

Theta -notation  theta notation  is called tight-bound because it s more precise than O-notation and  Omega -notation  omega notation     If I were lazy  I could say that binary search on a sorted array is O n2   O n3   and O 2n   and I would be technically correct in every case   That s because O-notation only specifies an upper bound  and binary search is bounded on the high side by all of those functions  just not very closely  These lazy estimates would be useless    Theta -notation solves this problem by combining O-notation and  Omega -notation  If I say that binary search is  Theta  log n   that gives you more precise information   It tells you that the algorithm is bounded on both sides by the given function  so it will never be significantly faster or slower than stated

User · Answer

The phrases minimum time and maximum time are a bit misleading here  When we talk about big O notations  it s not the actual time we are interested in  it is how the time increases when our input size gets bigger  And it s usually the average or worst case time we are talking about  not best case  which usually is not meaningful in solving our problems    Using the array search in the accepted answer to the other question as an example  The time it takes to find a particular number in list of size n is n 2   some constant in average  If you treat it as a function f n    n 2 some constant  it increases no faster than g n    n  in the sense as given by Charlie  Also  it increases no slower than g n  either  Hence  g n  is actually both an upper bound and a lower bound of f n  in Big-O notation  so the complexity of linear search is exactly n  meaning that it is Theta n     In this regard  the explanation in the accepted answer to the other question is not entirely correct  which claims that O n  is upper bound because the algorithm can run in constant time for some inputs  this is the best case I mentioned above  which is not really what we want to know about the running time

User · Answer

Big O is the upper bound  while Omega is the lower bound  Theta requires both Big O and Omega  so that s why it s referred to as a tight bound  it must be both the upper and lower bound    For example  an algorithm taking Omega n log n  takes at least n log n time  but has no upper limit  An algorithm taking Theta n log n  is far preferential since it takes at least n log n  Omega n log n  and no more than n log n  Big O n log n

User · Answer

The phrases minimum time and maximum time are a bit misleading here  When we talk about big O notations  it s not the actual time we are interested in  it is how the time increases when our input size gets bigger  And it s usually the average or worst case time we are talking about  not best case  which usually is not meaningful in solving our problems    Using the array search in the accepted answer to the other question as an example  The time it takes to find a particular number in list of size n is n 2   some constant in average  If you treat it as a function f n    n 2 some constant  it increases no faster than g n    n  in the sense as given by Charlie  Also  it increases no slower than g n  either  Hence  g n  is actually both an upper bound and a lower bound of f n  in Big-O notation  so the complexity of linear search is exactly n  meaning that it is Theta n     In this regard  the explanation in the accepted answer to the other question is not entirely correct  which claims that O n  is upper bound because the algorithm can run in constant time for some inputs  this is the best case I mentioned above  which is not really what we want to know about the running time

[big-o] What is the difference between lower bound and tight bound?

Examples related to big-o