What is the difference between T n and O n

Question

Sometimes I see T n  with the strange T symbol with something in the middle of it  and sometimes just O n   Is it just laziness of typing because nobody knows how to type this symbol  or does it mean something different

User · Answer

There s a simple way  a trick  I guess  to remember which notation means what   All of the Big-O notations can be considered to have a bar    When looking at a O  the bar is at the bottom  so it is an  asymptotic  lower bound   When looking at a T  the bar is obviously in the middle  So it is an  asymptotic  tight bound    When handwriting O  you usually finish at the top  and draw a squiggle  Therefore O n  is the upper bound of the function  To be fair  this one doesn t work with most fonts  but it is the original justification of the names

User · Answer

one is Big  O   one is Big Theta  http   en wikipedia org wiki Big O notation  Big O means your algorithm will execute in no more steps than in given expression n 2   Big Omega means your algorithm will execute in no fewer steps than in the given expression n 2   When both condition are true for the same expression  you can use the big theta notation

User · Answer

Conclusion  we regard big O  big   and big O as the same thing  Why  I will tell the reason below  Firstly  I will clarify one wrong statement  some people think that we just care the worst time complexity  so we always use big O instead of big    I will say this man is bullshitting  Upper and lower bound are used to describe one function  not used to describe the time complexity  The worst time function has its upper and lower bound  the best time function has its upper and lower bound too  In order to explain clearly the relation between big O and big    I will explain the relation between big O and small o first  From the definition  we can easily know that small o is a subset of big O  For example   T n   n 2   n  we can say T n  O n 2   T n  O n 3   T n  O n 4   But for small o  T n  o n 2  does not meet the definition of small o  So just T n  o n 3   T n  o n 4  are correct for small o  The redundant T n  O n 2  is what  It s big     Generally  we say big O is O n 2   hardly to say T n  O n 3   T n  O n 4   Why  Because we regard big O as big   subconsciously  Similarly  we also regard big O as big   subconsciously  In one word  big O  big   and big O are not the same thing from the definitions  but they are the same thing in our mouth and brain

User · Answer

Theta is a shorthand way of referring to a special situtation where the big O and Omega are the same   Thus  if one claims The Theta is expression q  then they are also necessarily claiming that Big O is expression q and Omega is expression q     Rough analogy   If  Theta claims   That animal has 5 legs   then it follows that  Big O is true   That animal has less than or equal to 5 legs    and Omega is true  That animal has more than or equal to 5 legs     It s only a rough analogy because the expressions aren t necessarily specific numbers  but instead functions of varying orders of magnitude such as log n   n  n 2   etc

User · Answer

f n  belongs to O n  if exists positive k as f n  lt  k n  f n  belongs to T n  if exists positive k1  k2 as k1 n lt  f n  lt  k2 n  Wikipedia article on Big O Notation

User · Answer

Using limits  Let s consider f n   gt  0 and g n   gt  0 for all n  It s ok to consider this  because the fastest real algorithm has at least one operation and completes its execution after the start  This will simplify the calculus  because we can use the value  f n   instead of the absolute value   f n       f n    O g n    General             f n       0   lim --------  lt  8     n 8   g n    For g n    n             f n       0   lim --------  lt  8     n 8    n   Examples       Expression               Value of the limit ------------------------------------------------ n          O n                       1 1 2 n      O n                      1 2 2 n        O n                       2 n log n    O n                       1 n          O n log n                 0 n          O n                        0 n          O nn                      0   Counterexamples       Expression                Value of the limit ------------------------------------------------- n          O log n                   8 1 2 n      O sqrt n                  8 2 n        O 1                       8 n log n    O log n                   8  f n    T g n    General             f n       0  lt  lim --------  lt  8     n 8   g n    For g n    n             f n       0  lt  lim --------  lt  8     n 8    n   Examples       Expression               Value of the limit ------------------------------------------------ n          T n                       1 1 2 n      T n                      1 2 2 n        T n                       2 n log n    T n                       1   Counterexamples       Expression                Value of the limit ------------------------------------------------- n          T log n                   8 1 2 n      T sqrt n                  8 2 n        T 1                       8 n log n    T log n                   8 n          T n log n                 0 n          T n                        0 n          T nn                      0

User · Answer

Theta is a shorthand way of referring to a special situtation where the big O and Omega are the same   Thus  if one claims The Theta is expression q  then they are also necessarily claiming that Big O is expression q and Omega is expression q     Rough analogy   If  Theta claims   That animal has 5 legs   then it follows that  Big O is true   That animal has less than or equal to 5 legs    and Omega is true  That animal has more than or equal to 5 legs     It s only a rough analogy because the expressions aren t necessarily specific numbers  but instead functions of varying orders of magnitude such as log n   n  n 2   etc

User · Answer

There s a simple way  a trick  I guess  to remember which notation means what   All of the Big-O notations can be considered to have a bar    When looking at a O  the bar is at the bottom  so it is an  asymptotic  lower bound   When looking at a T  the bar is obviously in the middle  So it is an  asymptotic  tight bound    When handwriting O  you usually finish at the top  and draw a squiggle  Therefore O n  is the upper bound of the function  To be fair  this one doesn t work with most fonts  but it is the original justification of the names

User · Answer

Conclusion  we regard big O  big   and big O as the same thing  Why  I will tell the reason below  Firstly  I will clarify one wrong statement  some people think that we just care the worst time complexity  so we always use big O instead of big    I will say this man is bullshitting  Upper and lower bound are used to describe one function  not used to describe the time complexity  The worst time function has its upper and lower bound  the best time function has its upper and lower bound too  In order to explain clearly the relation between big O and big    I will explain the relation between big O and small o first  From the definition  we can easily know that small o is a subset of big O  For example   T n   n 2   n  we can say T n  O n 2   T n  O n 3   T n  O n 4   But for small o  T n  o n 2  does not meet the definition of small o  So just T n  o n 3   T n  o n 4  are correct for small o  The redundant T n  O n 2  is what  It s big     Generally  we say big O is O n 2   hardly to say T n  O n 3   T n  O n 4   Why  Because we regard big O as big   subconsciously  Similarly  we also regard big O as big   subconsciously  In one word  big O  big   and big O are not the same thing from the definitions  but they are the same thing in our mouth and brain

User · Answer

A chart could make the previous answers easier to understand  T-Notation - Same order   O-Notation - Upper bound    In English  On the left  note that there is an upper bound and a lower bound that are both of the same order of magnitude  i e  g n     Ignore the constants  and if the upper bound and lower bound have the same order of magnitude  one can validly say f n    T g n   or f n  is in big theta of g n   Starting with the right  the simpler example  it is saying the upper bound g n  is simply the order of magnitude and ignores the constant c  just as all big O notation does

User · Answer

A chart could make the previous answers easier to understand  T-Notation - Same order   O-Notation - Upper bound    In English  On the left  note that there is an upper bound and a lower bound that are both of the same order of magnitude  i e  g n     Ignore the constants  and if the upper bound and lower bound have the same order of magnitude  one can validly say f n    T g n   or f n  is in big theta of g n   Starting with the right  the simpler example  it is saying the upper bound g n  is simply the order of magnitude and ignores the constant c  just as all big O notation does

User · Answer

There s a simple way  a trick  I guess  to remember which notation means what   All of the Big-O notations can be considered to have a bar    When looking at a O  the bar is at the bottom  so it is an  asymptotic  lower bound   When looking at a T  the bar is obviously in the middle  So it is an  asymptotic  tight bound    When handwriting O  you usually finish at the top  and draw a squiggle  Therefore O n  is the upper bound of the function  To be fair  this one doesn t work with most fonts  but it is the original justification of the names

User · Answer

Rather than provide a theoretical definition  which are beautifully summarized here already  I ll give a simple example   Assume the run time of f i  is O 1   Below is a code fragment whose asymptotic runtime is T n   It always calls the function f      n times  Both the lower and the upper bound is n   for int i 0  i lt n  i         f i       The second code fragment below has the asymptotic runtime of O n   It calls the function f      at most n times  The upper bound is n  but the lower bound could be O 1  or O log n    depending on what happens inside f2 i     for int i 0  i lt n  i         if  f2 i    break      f i

User · Answer

f n  belongs to O n  if exists positive k as f n  lt  k n  f n  belongs to T n  if exists positive k1  k2 as k1 n lt  f n  lt  k2 n  Wikipedia article on Big O Notation

User · Answer

f n  belongs to O n  if exists positive k as f n  lt  k n  f n  belongs to T n  if exists positive k1  k2 as k1 n lt  f n  lt  k2 n  Wikipedia article on Big O Notation

User · Answer

one is Big  O   one is Big Theta  http   en wikipedia org wiki Big O notation  Big O means your algorithm will execute in no more steps than in given expression n 2   Big Omega means your algorithm will execute in no fewer steps than in the given expression n 2   When both condition are true for the same expression  you can use the big theta notation

User · Answer

one is Big  O   one is Big Theta  http   en wikipedia org wiki Big O notation  Big O means your algorithm will execute in no more steps than in given expression n 2   Big Omega means your algorithm will execute in no fewer steps than in the given expression n 2   When both condition are true for the same expression  you can use the big theta notation

User · Answer

There s a simple way  a trick  I guess  to remember which notation means what   All of the Big-O notations can be considered to have a bar    When looking at a O  the bar is at the bottom  so it is an  asymptotic  lower bound   When looking at a T  the bar is obviously in the middle  So it is an  asymptotic  tight bound    When handwriting O  you usually finish at the top  and draw a squiggle  Therefore O n  is the upper bound of the function  To be fair  this one doesn t work with most fonts  but it is the original justification of the names

User · Answer

Rather than provide a theoretical definition  which are beautifully summarized here already  I ll give a simple example   Assume the run time of f i  is O 1   Below is a code fragment whose asymptotic runtime is T n   It always calls the function f      n times  Both the lower and the upper bound is n   for int i 0  i lt n  i         f i       The second code fragment below has the asymptotic runtime of O n   It calls the function f      at most n times  The upper bound is n  but the lower bound could be O 1  or O log n    depending on what happens inside f2 i     for int i 0  i lt n  i         if  f2 i    break      f i

User · Answer

Short explanation      If an algorithm is of T g n    it means that the running time of the algorithm as n  input size  gets larger is proportional to g n        If an algorithm is of O g n    it means that the running time of the algorithm as n gets larger is at most proportional to g n     Normally  even when people talk about O g n   they actually mean T g n   but technically  there is a difference      More technically   O n  represents upper bound  T n  means tight bound  O n  represents lower bound           f x    T g x   iff f x        O g x   and f x    O g x        Basically when we say an algorithm is of O n   it s also O n2   O n1000000   O 2n       but a T n  algorithm is not T n2    In fact  since f n    T g n   means for sufficiently large values of n  f n  can be bound within c1g n  and c2g n  for some values of c1 and c2  i e  the growth rate of f is asymptotically equal to g  g can be a lower bound and and an upper bound of f  This directly implies f can be a lower bound and an upper bound of g as well  Consequently      f x    T g x   iff g x    T f x     Similarly  to show f n    T g n    it s enough to show g is an upper bound of f  i e  f n    O g n    and f is a lower bound of g  i e  f n    O g n   which is the exact same thing as g n    O f n     Concisely      f x    T g x   iff f x    O g x   and g x    O f x       There are also little-oh and little-omega     notations representing loose upper and loose lower bounds of a function    To summarize      f x    O g x    big-oh  means that   the growth rate of f x  is   asymptotically less than or equal   to to the growth rate of g x        f x    O g x    big-omega  means   that the growth rate of f x  is   asymptotically greater than or   equal to the growth rate of g x       f x    o g x    little-oh  means that   the growth rate of f x  is   asymptotically less than the   growth rate of g x        f x      g x    little-omega  means   that the growth rate of f x  is   asymptotically greater than the   growth rate of g x       f x    T g x    theta  means that   the growth rate of f x  is   asymptotically equal to the   growth rate of g x    For a more detailed discussion  you can read the definition on Wikipedia or consult a classic textbook like Introduction to Algorithms by Cormen et al

User · Answer

Using limits  Let s consider f n   gt  0 and g n   gt  0 for all n  It s ok to consider this  because the fastest real algorithm has at least one operation and completes its execution after the start  This will simplify the calculus  because we can use the value  f n   instead of the absolute value   f n       f n    O g n    General             f n       0   lim --------  lt  8     n 8   g n    For g n    n             f n       0   lim --------  lt  8     n 8    n   Examples       Expression               Value of the limit ------------------------------------------------ n          O n                       1 1 2 n      O n                      1 2 2 n        O n                       2 n log n    O n                       1 n          O n log n                 0 n          O n                        0 n          O nn                      0   Counterexamples       Expression                Value of the limit ------------------------------------------------- n          O log n                   8 1 2 n      O sqrt n                  8 2 n        O 1                       8 n log n    O log n                   8  f n    T g n    General             f n       0  lt  lim --------  lt  8     n 8   g n    For g n    n             f n       0  lt  lim --------  lt  8     n 8    n   Examples       Expression               Value of the limit ------------------------------------------------ n          T n                       1 1 2 n      T n                      1 2 2 n        T n                       2 n log n    T n                       1   Counterexamples       Expression                Value of the limit ------------------------------------------------- n          T log n                   8 1 2 n      T sqrt n                  8 2 n        T 1                       8 n log n    T log n                   8 n          T n log n                 0 n          T n                        0 n          T nn                      0

User · Answer

f n  belongs to O n  if exists positive k as f n  lt  k n  f n  belongs to T n  if exists positive k1  k2 as k1 n lt  f n  lt  k2 n  Wikipedia article on Big O Notation

User · Answer

Short explanation      If an algorithm is of T g n    it means that the running time of the algorithm as n  input size  gets larger is proportional to g n        If an algorithm is of O g n    it means that the running time of the algorithm as n gets larger is at most proportional to g n     Normally  even when people talk about O g n   they actually mean T g n   but technically  there is a difference      More technically   O n  represents upper bound  T n  means tight bound  O n  represents lower bound           f x    T g x   iff f x        O g x   and f x    O g x        Basically when we say an algorithm is of O n   it s also O n2   O n1000000   O 2n       but a T n  algorithm is not T n2    In fact  since f n    T g n   means for sufficiently large values of n  f n  can be bound within c1g n  and c2g n  for some values of c1 and c2  i e  the growth rate of f is asymptotically equal to g  g can be a lower bound and and an upper bound of f  This directly implies f can be a lower bound and an upper bound of g as well  Consequently      f x    T g x   iff g x    T f x     Similarly  to show f n    T g n    it s enough to show g is an upper bound of f  i e  f n    O g n    and f is a lower bound of g  i e  f n    O g n   which is the exact same thing as g n    O f n     Concisely      f x    T g x   iff f x    O g x   and g x    O f x       There are also little-oh and little-omega     notations representing loose upper and loose lower bounds of a function    To summarize      f x    O g x    big-oh  means that   the growth rate of f x  is   asymptotically less than or equal   to to the growth rate of g x        f x    O g x    big-omega  means   that the growth rate of f x  is   asymptotically greater than or   equal to the growth rate of g x       f x    o g x    little-oh  means that   the growth rate of f x  is   asymptotically less than the   growth rate of g x        f x      g x    little-omega  means   that the growth rate of f x  is   asymptotically greater than the   growth rate of g x       f x    T g x    theta  means that   the growth rate of f x  is   asymptotically equal to the   growth rate of g x    For a more detailed discussion  you can read the definition on Wikipedia or consult a classic textbook like Introduction to Algorithms by Cormen et al

User · Answer

Short explanation      If an algorithm is of T g n    it means that the running time of the algorithm as n  input size  gets larger is proportional to g n        If an algorithm is of O g n    it means that the running time of the algorithm as n gets larger is at most proportional to g n     Normally  even when people talk about O g n   they actually mean T g n   but technically  there is a difference      More technically   O n  represents upper bound  T n  means tight bound  O n  represents lower bound           f x    T g x   iff f x        O g x   and f x    O g x        Basically when we say an algorithm is of O n   it s also O n2   O n1000000   O 2n       but a T n  algorithm is not T n2    In fact  since f n    T g n   means for sufficiently large values of n  f n  can be bound within c1g n  and c2g n  for some values of c1 and c2  i e  the growth rate of f is asymptotically equal to g  g can be a lower bound and and an upper bound of f  This directly implies f can be a lower bound and an upper bound of g as well  Consequently      f x    T g x   iff g x    T f x     Similarly  to show f n    T g n    it s enough to show g is an upper bound of f  i e  f n    O g n    and f is a lower bound of g  i e  f n    O g n   which is the exact same thing as g n    O f n     Concisely      f x    T g x   iff f x    O g x   and g x    O f x       There are also little-oh and little-omega     notations representing loose upper and loose lower bounds of a function    To summarize      f x    O g x    big-oh  means that   the growth rate of f x  is   asymptotically less than or equal   to to the growth rate of g x        f x    O g x    big-omega  means   that the growth rate of f x  is   asymptotically greater than or   equal to the growth rate of g x       f x    o g x    little-oh  means that   the growth rate of f x  is   asymptotically less than the   growth rate of g x        f x      g x    little-omega  means   that the growth rate of f x  is   asymptotically greater than the   growth rate of g x       f x    T g x    theta  means that   the growth rate of f x  is   asymptotically equal to the   growth rate of g x    For a more detailed discussion  you can read the definition on Wikipedia or consult a classic textbook like Introduction to Algorithms by Cormen et al

User · Answer

one is Big  O   one is Big Theta  http   en wikipedia org wiki Big O notation  Big O means your algorithm will execute in no more steps than in given expression n 2   Big Omega means your algorithm will execute in no fewer steps than in the given expression n 2   When both condition are true for the same expression  you can use the big theta notation

User · Answer

Short explanation      If an algorithm is of T g n    it means that the running time of the algorithm as n  input size  gets larger is proportional to g n        If an algorithm is of O g n    it means that the running time of the algorithm as n gets larger is at most proportional to g n     Normally  even when people talk about O g n   they actually mean T g n   but technically  there is a difference      More technically   O n  represents upper bound  T n  means tight bound  O n  represents lower bound           f x    T g x   iff f x        O g x   and f x    O g x        Basically when we say an algorithm is of O n   it s also O n2   O n1000000   O 2n       but a T n  algorithm is not T n2    In fact  since f n    T g n   means for sufficiently large values of n  f n  can be bound within c1g n  and c2g n  for some values of c1 and c2  i e  the growth rate of f is asymptotically equal to g  g can be a lower bound and and an upper bound of f  This directly implies f can be a lower bound and an upper bound of g as well  Consequently      f x    T g x   iff g x    T f x     Similarly  to show f n    T g n    it s enough to show g is an upper bound of f  i e  f n    O g n    and f is a lower bound of g  i e  f n    O g n   which is the exact same thing as g n    O f n     Concisely      f x    T g x   iff f x    O g x   and g x    O f x       There are also little-oh and little-omega     notations representing loose upper and loose lower bounds of a function    To summarize      f x    O g x    big-oh  means that   the growth rate of f x  is   asymptotically less than or equal   to to the growth rate of g x        f x    O g x    big-omega  means   that the growth rate of f x  is   asymptotically greater than or   equal to the growth rate of g x       f x    o g x    little-oh  means that   the growth rate of f x  is   asymptotically less than the   growth rate of g x        f x      g x    little-omega  means   that the growth rate of f x  is   asymptotically greater than the   growth rate of g x       f x    T g x    theta  means that   the growth rate of f x  is   asymptotically equal to the   growth rate of g x    For a more detailed discussion  you can read the definition on Wikipedia or consult a classic textbook like Introduction to Algorithms by Cormen et al

[big-o] What is the difference between T(n) and O(n)?

Examples related to big-o

Examples related to time-complexity

Examples related to notation

Examples related to big-theta