The Stack Overflow podcast is back! Listen to an interview with our new CEO.
7 correct misconception and add more details
source | link

(Note: in the sense employed here, the asymptotic functions are only close to the original function after correcting for some constant nonzero factor, as all the three big-O/Θ/Ω notations disregard this constant factors from their consideration.)

First off, be warned that in informal literature, “Big-O” is often treated as a synonym for Big-Θ, perhaps because Greek letters are tricky to type. So if someone out of the blue asks you for the Big-O of an algorithm, they probably want you to calculateits Big-Θ.

No. Big-O and its family of notations talk about a specific mathematical function. They are mathematical tools employed to help characterize the efficiency of algorithms, but the notion of best/average/worst-case is unrelated to the theory of growth rates describedescribed here.

To talk about the Big-O of an algorithm, you are required toone must commit to a particularspecific mathematical model of an algorithm with exactly one parameter n, which is supposed to describe the “size” of the input, in whatever sense is relevant to the problemuseful. But in the real world, input hasinputs have much more structure than just its lengththeir lengths. If this was a sorting algorithm, I could feed in a string "abcdef"the strings "abcdef", "fedcba""fedcba", or "dbafce""dbafce". All of them are of length 6, but one of them is already sorted, one is reversed, and anotherthe last is just a random jumble. Some sorting algorithms (like Timsort) work better if the input is already jumbledsorted. But how does one incorporate this inhomogeneity into a mathematical model?

The typicallytypical approach is to justsimply assume the input comes from some random, probabilistic distribution. Then, what you do is you take the statistical average of the algorithm's complexity applied toover all inputs with length n. This gives you an average-case complexity model of the algorithm. From here, you can then use the Big-O/Θ/Ω notations as usual to describe the average case behavior.

But if you are concerned about denial-of-service attacks, then you might have to be more pessimistic. In this case, you'dit is safer to assume that the only inputs are those that cause the most amount of grief to your algorithm. This gives you a worst-case complexity model of the algorithm. Then Afterwards, you can talk about Big-O/Θ/Ω etc of the worst-caseworst-case model.

Similarly, you can also focus your interest exclusively to the inputs that your algorithm has the least amount of trouble with, to arrive at a best-casebest-case model, then look at Big-O/Θ/Ω etc.

First off, be warned that in informal literature, “Big-O” is often treated as a synonym for Big-Θ, perhaps because Greek letters are tricky to type. So if someone out of the blue asks you the Big-O of an algorithm, they probably want you to calculate Big-Θ.

No. Big-O and its family of notations talk about a specific mathematical function. They are mathematical tools employed help characterize the efficiency of algorithms, but the notion of best/average/worst-case is unrelated to the theory of growth rates describe here.

To talk about the Big-O of an algorithm, you are required to commit to a particular mathematical model of an algorithm with exactly one parameter n, which is supposed to describe the “size” of the input, in whatever sense is relevant to the problem. But in the real world, input has much more structure than just its length. If this was a sorting algorithm, I could feed in a string "abcdef", "fedcba", or "dbafce". All of them are of length 6, but one of them is already sorted, one is reversed, and another is just a random jumble. Some sorting algorithms (like Timsort) work better if the input is already jumbled. But how does one incorporate this into a mathematical model?

The typically approach is to just assume the input comes from some random, probabilistic distribution. Then, what you do is you take the statistical average of the algorithm's complexity applied to all inputs with length n. This gives you an average-case complexity model of the algorithm. From here, you can then use the Big-O/Θ/Ω notations as usual to describe the average case behavior.

But if you are concerned about denial-of-service attacks, then you might have to be more pessimistic. In this case, you'd assume that the only inputs are those that cause the most amount of grief to your algorithm. This gives you a worst-case complexity model of the algorithm. Then you can talk about Big-O/Θ/Ω etc of the worst-case model.

Similarly, you can also focus your interest exclusively to the inputs that your algorithm has the least amount of trouble with, to arrive at a best-case model, then look at Big-O/Θ/Ω etc.

(Note: in the sense employed here, the asymptotic functions are only close to the original function after correcting for some constant nonzero factor, as all the three big-O/Θ/Ω notations disregard this constant factors from their consideration.)

First off, be warned that in informal literature, “Big-O” is often treated as a synonym for Big-Θ, perhaps because Greek letters are tricky to type. So if someone out of the blue asks you for the Big-O of an algorithm, they probably want its Big-Θ.

No. Big-O and its family of notations talk about a specific mathematical function. They are mathematical tools employed to help characterize the efficiency of algorithms, but the notion of best/average/worst-case is unrelated to the theory of growth rates described here.

To talk about the Big-O of an algorithm, one must commit to a specific mathematical model of an algorithm with exactly one parameter n, which is supposed to describe the “size” of the input, in whatever sense is useful. But in the real world, inputs have much more structure than just their lengths. If this was a sorting algorithm, I could feed in the strings "abcdef", "fedcba", or "dbafce". All of them are of length 6, but one of them is already sorted, one is reversed, and the last is just a random jumble. Some sorting algorithms (like Timsort) work better if the input is already sorted. But how does one incorporate this inhomogeneity into a mathematical model?

The typical approach is to simply assume the input comes from some random, probabilistic distribution. Then, you average the algorithm's complexity over all inputs with length n. This gives you an average-case complexity model of the algorithm. From here, you can use the Big-O/Θ/Ω notations as usual to describe the average case behavior.

But if you are concerned about denial-of-service attacks, then you might have to be more pessimistic. In this case, it is safer to assume that the only inputs are those that cause the most amount of grief to your algorithm. This gives you a worst-case complexity model of the algorithm. Afterwards, you can talk about Big-O/Θ/Ω etc of the worst-case model.

Similarly, you can also focus your interest exclusively to the inputs that your algorithm has the least amount of trouble with to arrive at a best-case model, then look at Big-O/Θ/Ω etc.

6 correct misconception and add more details
source | link

Given a function f(n) that implementsdescribes the amount of resources (CPU time, RAM, disk space, etc) consumed by an algorithm when applied to an input of size of n, we define up to three asymptotic notations for measuringdescribing its performance for large n. 

An asymptote (or asymptotic function) is simply some other function (or relation) g(n) that f(n) gets increasingly close to as n grows larger and larger, but never quite reaches. This The advantage of talking about asymptotic functions is used to determine bounding functions that containthey are generally much simpler to talk about even if the expression for f(n) is extremely complicated. Asymptotic functions are used as part of the bounding notations that restrict f(n) above or below.

What are the three asymptotic functionsbounding notations and how are they different?

Big-O notationAll three notations is concerned with the worst case complexity of an algorithmused like this: it is an upper-bound on the complexity of f(n).

Big-Ω (Omega) is the opposite: it is the best casef(n) = O(g(n)). An algorithm may be really efficient for certain inputs, or it may take just as long as the worst case. Regardless, this is the lower-bound on a complexity of

where f(n) here is the function of interest, and g(n) is some other asymptotic function that you are trying to approximate f(n) with. This should not be taken as an equality in a rigorous sense, but a formal statement between how fast f(n) grows with respect to n in comparison to g(n), as n becomes large. Purists will often use the alternative notation f(n) ∈ O(g(n)) to emphasize that the symbol O(g(n)) is really a whole family of functions that share a common growth rate.

Big-ϴ (Theta) is applicable to a function where the best and worst case arenotation states an equality on the same, differing only bygrowth of f(n) up to a constant factor (more on this later). If a function scales the same regardless of the input, it has O(n) = Ω(n) → ϴ(n) It behaves similar to an = operator for growth rates.

What type of complexity do they measure?

Big-O notation describes an upper-bound on the growth of f(n). It behaves similar to a operator for growth rates.

Complexity is typically measured in the amountBig-Ω (Omega) notation describes a lower-bound on a growth of time for f(n). It behaves similar to executea operator for growth rates.

There are many other asymptotic notations, but they do not occur nearly as it scales withoften in computer science literature.

Big-O notations and its ilk are often as a way to compare the input ntime complexity, or more specifically,.

What is time complexity?

Time complexity is a fancy term for the numberamount of stepstime T(n) to complete theit takes for an algorithm to execute as a function of its input size n. However, it may also measure This can be measured in the amount of memoryreal time (storagee.g. seconds) required to complete, the number of CPU instructions, etc. Usually it is assumed that the algorithm will run on your everyday von Neumann architecture computer. But of course you can use time complexity to talk about more exotic computing systems, where things may be different!

It is also common to talk about space complexity using Big-O notation. Space complexity is the amount of memory (storage) required to complete the algorithm, which could be RAM, disk, etc.

Calculating Big-Oϴ

Calculating the Big-Oϴ of an algorithm is a topic that can fill a small textbook or roughly half a semester of undergraduate class: this section will cover the basics.

T(n) = n2 → O∈ ϴ(n2)
T(n) = 2n2 → O∈ ϴ(n2)

T(n) = 2n2 + 4n + 7 → O∈ ϴ(n2)

Calculating Big-Ω and Big-ϴO

Calculating BigFirst off, be warned that in informal literature, “Big-ΩO” is similar tooften treated as a synonym for Big-OΘ, except one figures out "what is the best outcome at each step?" This is normally done if there is any way to shortcut the logic: is there a decision at a particular step instead of blindly iterating? If it is possibleperhaps because Greek letters are tricky to eliminate parttype. So if someone out of the input,blue asks you the bestBig-case may be better than the worstO of an algorithm, they probably want you to calculate Big-caseΘ.

It may be the case that an algorithm is always the same complexity. The bestNow if you really do want to calculate Big-Ω and worst cases have the same algorithmic complexity: perhaps they differ only by a constant. In the asymptotic measurement, they scaleBig-O in the same way. For exampleformal senses defined earlier, searchingyou have a major problem: there are infinitely many Big-Ω and Big-O descriptions for any given function! It's like asking what the minimumnumbers that are less than or maximum value in an unsorted listequal to 42 are. There are alwaysmany requirespossibilities.

For an algorithm with T(n) ∈ ϴ(n2) time: such an algorithm is Ω(n) and O(n). If this is the case, any of the algorithm is also ϴ(n): its upper and lower boundsfollowing are the same, ϴ(n).formally valid statements to make:

  • T(n) ∈ O(n2)
  • T(n) ∈ O(n3)
  • T(n) ∈ O(n5)
  • T(n) ∈ O(n12345 × en)
  • T(n) ∈ Ω(n2)
  • T(n) ∈ Ω(n)
  • T(n) ∈ Ω(log(n))
  • T(n) ∈ Ω(log(log(n)))
  • T(n) ∈ Ω(1)

But it is incorrect to state T(n) ∈ O(n) or T(n) ∈ Ω(n3).

  • OΘ(1) - constant. For example, picking the first number in a list will always take the same amount of time.

  • OΘ(n) - linear. For example, iterating a list will always take time proportional to the list size, n.

  • OΘ(log n(n)) - logarithmic (base normally does not matter). Algorithms that divide the input space at each step, such as binary search, are examples.

  • OΘ(n × log n(n)) - linear times logarithmic (“linearithmic”). These algorithms typically divide and conquer (log n(n)) while still iterating (n) all of the input. Many popular sorting algorithms (merge sort, Timsort) fall into this category.

  • OΘ(nm) - polynomial (n raised to any constant m). This is a very common complexity class, often found in nested loops.

  • OΘ(mn) - exponential (any constant m raised to n). Many recursive and graph algorithms fall into this category.

  • OΘ(n!) - factorial. Certain graph and combinatorial algorithms are factorial complexity.

Does this have anything to do with best/average/worst case?

No. Big-O and its family of notations talk about a specific mathematical function. They are mathematical tools employed help characterize the efficiency of algorithms, but the notion of best/average/worst-case is unrelated to the theory of growth rates describe here.

To talk about the Big-O of an algorithm, you are required to commit to a particular mathematical model of an algorithm with exactly one parameter n, which is supposed to describe the “size” of the input, in whatever sense is relevant to the problem. But in the real world, input has much more structure than just its length. If this was a sorting algorithm, I could feed in a string "abcdef", "fedcba", or "dbafce". All of them are of length 6, but one of them is already sorted, one is reversed, and another is just a random jumble. Some sorting algorithms (like Timsort) work better if the input is already jumbled. But how does one incorporate this into a mathematical model?

The typically approach is to just assume the input comes from some random, probabilistic distribution. Then, what you do is you take the statistical average of the algorithm's complexity applied to all inputs with length n. This gives you an average-case complexity model of the algorithm. From here, you can then use the Big-O/Θ/Ω notations as usual to describe the average case behavior.

But if you are concerned about denial-of-service attacks, then you might have to be more pessimistic. In this case, you'd assume that the only inputs are those that cause the most amount of grief to your algorithm. This gives you a worst-case complexity model of the algorithm. Then you can talk about Big-O/Θ/Ω etc of the worst-case model.

Similarly, you can also focus your interest exclusively to the inputs that your algorithm has the least amount of trouble with, to arrive at a best-case model, then look at Big-O/Θ/Ω etc.

Given a function f(n) that implements an algorithm, we define up to three asymptotic notations for measuring its performance. An asymptote is simply some other function (or relation) g(n) that f(n) gets close to, but never quite reaches. This is used to determine bounding functions that contain f(n) above or below.

What are the three asymptotic functions and how are they different?

Big-O notation is concerned with the worst case complexity of an algorithm: it is an upper-bound on the complexity of f(n).

Big-Ω (Omega) is the opposite: it is the best case. An algorithm may be really efficient for certain inputs, or it may take just as long as the worst case. Regardless, this is the lower-bound on a complexity of f(n).

Big-ϴ (Theta) is applicable to a function where the best and worst case are the same, differing only by a constant factor (more on this later). If a function scales the same regardless of the input, it has O(n) = Ω(n) → ϴ(n)

What type of complexity do they measure?

Complexity is typically measured in the amount of time for f(n) to execute as it scales with the input n, or more specifically, the number of steps T(n) to complete the algorithm. However, it may also measure the amount of memory (storage) required to complete the algorithm.

Calculating Big-O

Calculating the Big-O of an algorithm is a topic that can fill a small textbook or roughly half a semester of undergraduate class: this section will cover the basics.

T(n) = n2 → O(n2)
T(n) = 2n2 → O(n2)

T(n) = 2n2 + 4n + 7 → O(n2)

Calculating Big-Ω and Big-ϴ

Calculating Big-Ω is similar to Big-O, except one figures out "what is the best outcome at each step?" This is normally done if there is any way to shortcut the logic: is there a decision at a particular step instead of blindly iterating? If it is possible to eliminate part of the input, the best-case may be better than the worst-case.

It may be the case that an algorithm is always the same complexity. The best and worst cases have the same algorithmic complexity: perhaps they differ only by a constant. In the asymptotic measurement, they scale the same way. For example, searching for the minimum or maximum value in an unsorted list always requires n time: such an algorithm is Ω(n) and O(n). If this is the case, the algorithm is also ϴ(n): its upper and lower bounds are the same, ϴ(n).

  • O(1) - constant. For example, picking the first number in a list will always take the same amount of time.

  • O(n) - linear. For example, iterating a list will always take time proportional to the list size, n.

  • O(log n) - logarithmic (base normally does not matter). Algorithms that divide the input space at each step, such as binary search, are examples.

  • O(n log n) - linear times logarithmic. These algorithms typically divide and conquer (log n) while still iterating (n) all of the input. Many popular sorting algorithms (merge sort, Timsort) fall into this category.

  • O(nm) - polynomial (n raised to any constant m). This is a very common complexity class, often found in nested loops.

  • O(mn) - exponential (any constant m raised to n). Many recursive and graph algorithms fall into this category.

  • O(n!) - factorial. Certain graph and combinatorial algorithms are factorial complexity.

Given a function f(n) that describes the amount of resources (CPU time, RAM, disk space, etc) consumed by an algorithm when applied to an input of size of n, we define up to three asymptotic notations for describing its performance for large n. 

An asymptote (or asymptotic function) is simply some other function (or relation) g(n) that f(n) gets increasingly close to as n grows larger and larger, but never quite reaches. The advantage of talking about asymptotic functions is that they are generally much simpler to talk about even if the expression for f(n) is extremely complicated. Asymptotic functions are used as part of the bounding notations that restrict f(n) above or below.

What are the three asymptotic bounding notations and how are they different?

All three notations is used like this:

f(n) = O(g(n))

where f(n) here is the function of interest, and g(n) is some other asymptotic function that you are trying to approximate f(n) with. This should not be taken as an equality in a rigorous sense, but a formal statement between how fast f(n) grows with respect to n in comparison to g(n), as n becomes large. Purists will often use the alternative notation f(n) ∈ O(g(n)) to emphasize that the symbol O(g(n)) is really a whole family of functions that share a common growth rate.

Big-ϴ (Theta) notation states an equality on the growth of f(n) up to a constant factor (more on this later). It behaves similar to an = operator for growth rates.

Big-O notation describes an upper-bound on the growth of f(n). It behaves similar to a operator for growth rates.

Big-Ω (Omega) notation describes a lower-bound on a growth of f(n). It behaves similar to a operator for growth rates.

There are many other asymptotic notations, but they do not occur nearly as often in computer science literature.

Big-O notations and its ilk are often as a way to compare the time complexity.

What is time complexity?

Time complexity is a fancy term for the amount of time T(n) it takes for an algorithm to execute as a function of its input size n. This can be measured in the amount of real time (e.g. seconds), the number of CPU instructions, etc. Usually it is assumed that the algorithm will run on your everyday von Neumann architecture computer. But of course you can use time complexity to talk about more exotic computing systems, where things may be different!

It is also common to talk about space complexity using Big-O notation. Space complexity is the amount of memory (storage) required to complete the algorithm, which could be RAM, disk, etc.

Calculating Big-ϴ

Calculating the Big-ϴ of an algorithm is a topic that can fill a small textbook or roughly half a semester of undergraduate class: this section will cover the basics.

T(n) = n2 ∈ ϴ(n2)
T(n) = 2n2 ∈ ϴ(n2)

T(n) = 2n2 + 4n + 7 ∈ ϴ(n2)

Calculating Big-Ω and Big-O

First off, be warned that in informal literature, “Big-O” is often treated as a synonym for Big-Θ, perhaps because Greek letters are tricky to type. So if someone out of the blue asks you the Big-O of an algorithm, they probably want you to calculate Big-Θ.

Now if you really do want to calculate Big-Ω and Big-O in the formal senses defined earlier, you have a major problem: there are infinitely many Big-Ω and Big-O descriptions for any given function! It's like asking what the numbers that are less than or equal to 42 are. There are many possibilities.

For an algorithm with T(n) ∈ ϴ(n2), any of the following are formally valid statements to make:

  • T(n) ∈ O(n2)
  • T(n) ∈ O(n3)
  • T(n) ∈ O(n5)
  • T(n) ∈ O(n12345 × en)
  • T(n) ∈ Ω(n2)
  • T(n) ∈ Ω(n)
  • T(n) ∈ Ω(log(n))
  • T(n) ∈ Ω(log(log(n)))
  • T(n) ∈ Ω(1)

But it is incorrect to state T(n) ∈ O(n) or T(n) ∈ Ω(n3).

  • Θ(1) - constant. For example, picking the first number in a list will always take the same amount of time.

  • Θ(n) - linear. For example, iterating a list will always take time proportional to the list size, n.

  • Θ(log(n)) - logarithmic (base normally does not matter). Algorithms that divide the input space at each step, such as binary search, are examples.

  • Θ(n × log(n)) - linear times logarithmic (“linearithmic”). These algorithms typically divide and conquer (log(n)) while still iterating (n) all of the input. Many popular sorting algorithms (merge sort, Timsort) fall into this category.

  • Θ(nm) - polynomial (n raised to any constant m). This is a very common complexity class, often found in nested loops.

  • Θ(mn) - exponential (any constant m raised to n). Many recursive and graph algorithms fall into this category.

  • Θ(n!) - factorial. Certain graph and combinatorial algorithms are factorial complexity.

Does this have anything to do with best/average/worst case?

No. Big-O and its family of notations talk about a specific mathematical function. They are mathematical tools employed help characterize the efficiency of algorithms, but the notion of best/average/worst-case is unrelated to the theory of growth rates describe here.

To talk about the Big-O of an algorithm, you are required to commit to a particular mathematical model of an algorithm with exactly one parameter n, which is supposed to describe the “size” of the input, in whatever sense is relevant to the problem. But in the real world, input has much more structure than just its length. If this was a sorting algorithm, I could feed in a string "abcdef", "fedcba", or "dbafce". All of them are of length 6, but one of them is already sorted, one is reversed, and another is just a random jumble. Some sorting algorithms (like Timsort) work better if the input is already jumbled. But how does one incorporate this into a mathematical model?

The typically approach is to just assume the input comes from some random, probabilistic distribution. Then, what you do is you take the statistical average of the algorithm's complexity applied to all inputs with length n. This gives you an average-case complexity model of the algorithm. From here, you can then use the Big-O/Θ/Ω notations as usual to describe the average case behavior.

But if you are concerned about denial-of-service attacks, then you might have to be more pessimistic. In this case, you'd assume that the only inputs are those that cause the most amount of grief to your algorithm. This gives you a worst-case complexity model of the algorithm. Then you can talk about Big-O/Θ/Ω etc of the worst-case model.

Similarly, you can also focus your interest exclusively to the inputs that your algorithm has the least amount of trouble with, to arrive at a best-case model, then look at Big-O/Θ/Ω etc.

5 added 32 characters in body
source | link
  • O(1) - constant. For example, picking the first number in a list will always take the same amount of time.

  • O(n) - linear. For example, iterating a list will always take time proportional to the list size, n.

  • O(log n) - logarithmic (base normally does not matter). Algorithms that divide the input space at each step, such as binary search, are examples.

  • O(n log n) - linear times logarithmic. These algorithms typically divide and conquer (log n) while still iterating (n) all of the input. Many popular sorting algorithms (merge sort, Timsort) fall into this category.

  • O(nm) - polynomial (n raised to any constant m). This is a very common complexity class, often found in nested loops.

  • O(mn) - exponential (any constant m raised to n). Many exhaustiverecursive and graph algorithms fall into this category.

  • O(n!) - factorial. Certain graph and combinatorial algorithms are factorial complexity.

  • O(1) - constant. For example, picking the first number in a list will always take the same amount of time.

  • O(n) - linear. For example, iterating a list will always take time proportional to the list size, n.

  • O(log n) - logarithmic (base normally does not matter). Algorithms that divide the input space at each step, such as binary search, are examples.

  • O(n log n) - linear times logarithmic. These algorithms typically divide and conquer (log n) while still iterating (n) all of the input. Many popular sorting algorithms (merge sort, Timsort) fall into this category.

  • O(nm) - polynomial (n raised to any constant m). This is a very common complexity class.

  • O(mn) - exponential (any constant m raised to n). Many exhaustive graph algorithms fall into this category.

  • O(n!) - factorial. Certain graph and combinatorial algorithms are factorial complexity.

  • O(1) - constant. For example, picking the first number in a list will always take the same amount of time.

  • O(n) - linear. For example, iterating a list will always take time proportional to the list size, n.

  • O(log n) - logarithmic (base normally does not matter). Algorithms that divide the input space at each step, such as binary search, are examples.

  • O(n log n) - linear times logarithmic. These algorithms typically divide and conquer (log n) while still iterating (n) all of the input. Many popular sorting algorithms (merge sort, Timsort) fall into this category.

  • O(nm) - polynomial (n raised to any constant m). This is a very common complexity class, often found in nested loops.

  • O(mn) - exponential (any constant m raised to n). Many recursive and graph algorithms fall into this category.

  • O(n!) - factorial. Certain graph and combinatorial algorithms are factorial complexity.

4 Added info about ϴ.
source | link
3 Quick sort has an expected time of (n log n), but worst case is O(n**2). Timsort is O(n log n).
source | link
2 added 329 characters in body
source | link
1
source | link
    Post Made Community Wiki by user22815