6 ms·

I'm starting to question my understanding of algorithmic complexity, the author says things like "complexity being worst case O(n \log n)" and seems to talk abo

I'm starting to question my understanding of algorithmic complexity, the author says things like "complexity being worst case O(n \log n)" and seems to talk about big O notation used for average cases as well. I've learned that big O notation is always and exclusively about the worst case, for average and best cases we use Theta Θ and Omega Ω, respectively. Do people not follow these definitions strictly? Has the author committed a mistake or am I missing something? I did experience an interviewer once saying that my complexity analysis was wrong as the worst case would be extremely rare to hit, I did try to explain nicely that big O notation is always about the worst case, and that they were thinking about big Theta instead, now I wonder if I was wrong.

waynecochran 4y ago
You are mixing two things together. The "average/expected case" and the "worst case" are two different functions, each with their own O, Θ, Ω.
SQueeeeeL 4y ago
You should look into amortized complexity. That's the formalized name for worst case runtime over multiple trials.
bsedlm 4y ago
In my opinion, nothing about big-O and related omega, theta, etc, is at all strict. Maybe I value "pure symbolic clairty" too much. I do see a very pragmatic usefullness to the complexity notation.
larsrc 4y ago
There are variations, that's what we learned back at Uni. Expected O(f(n)), average O(f(n)), amortised O(f(n)), even expected amortised O(f(n)). "Expected" implied a randomised algorithm.
- tsimionescu 4y ago
  > "Expected" implied a randomised algorithm. Not necessarily. It can be the "expected" number of steps over the range of unknown inputs even for a deterministic algorithm.
vmsp 4y ago
In school, we used big O notation for all cases. I've never heard about theta or omega notation. Wikipedia's bubble sort page -- as an example -- also uses it for all cases. https://en.wikipedia.org/wiki/Bubble_sort https://en.wikipedia.org/wiki/Bubble_sort
- rockinghigh 4y ago
  You can see the list of notations here: https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann–Landau_notations https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm...
londons_explore 4y ago
Computer scientists stole some notation from mathematicians, but then slightly changed and substantially slackened the definition...
- tsimionescu 4y ago
  No, not really. CS and other branches of maths are using the exact same definitions of O,o,Θ, and ω. It is true that Ω is used with a different definition in CS, but it's stricter not more slack. As explained elsewhere though, they are not notations for algorithmic complexity, they are notations for function categorization. It just happens that a common use for this notation in CS is to categorize the function "best/average/worse/... case complexity of an algorithm", but they are also used for other purposes.
  - ufo 4y ago
    In my experience, a lot of the time when programmers say big O, they actually mean big Theta...
    - adrianN 4y ago
      Programmers need not be very good computer scientists. The actual scientists publishing papers on algorithms usually get it right.
    - tsimionescu 4y ago
      Yes, I agree with that. However, if f(n)=Theta(n) => f(n)=O(n), so they are usually not wrong, technically, just unnecessarily broad.
powersnail 4y ago
I think you are mistaken here. The concept of worst/best/amortized case is different from O/Theta/Omega. The latter is about the direction with which it is bounding. Big O/Theta/Omega denotes sets of functions, and each of them can be applied to best/worst/amortized complexity analysis.
karpierz 4y ago
Theta(X) is not "average case" behaviour, it means "both Omega(X) and O(X)". Ex: merge sort is Theta(n log(n)), but quick sort is not. The author is likely saying "worst case O(n log(n))" as redundancy to emphasize that this is worst case behaviour.
- tsimionescu 4y ago
  It's not redundant. You can have "average case O(n log(n))" but "worse case O(n^2)", like quicksort does. Depending on the pivot function, that "worse case" can be more or less common.
  - karpierz 4y ago
    It is not redundant to say "average case O(n log(n))". It's not formally a correct usage of O(). But colloquially, it means that the average number of operations over all possible inputs on length n is X. It is redundant to say "worst case O(n^2)". By definition, O(X) means that the maximum of the number of operations over all possible inputs of length n is at most X.
    - Kranar 4y ago
      You are incorrect about this. Worst case and Big O are independent of one another. The O, Ω, Θ, etc... are about describing bounds where O(f) is used for the set of asymptotic upper bounds on f, Ω(f) is the set of asymptotic lower bounds on f, and Θ(f) is the intersection of O(f) and Ω(f). Typically f is used to describe space or time complexity of an algorithm, but it can be used for any function that maps positive integers to the non-negative real numbers. You can make any combination of best case/worst case/average case with O, Ω, Θ. In fact, you can even consider other cases as well such as amortized cases, 90th percentile cases, any case you want to investigate that can be defined as a function from positive integers to non-negative real numbers can be classified as having an asymptotic upper bound, lower bound, or tight bound.
      - karpierz 4y ago
Corence 4y ago
O, Theta, and Omega are independent from best, worst, and average case. You can mathematically establish upper, lower, or exact bounds on any of the average, best, or worst cases. It is perfectly valid to say "the best case is O(n)" which means the best case scales no worse than linearly. The "no worse" here is not describing the best case, but rather the strictness of your bound. You could say a sort algorithm is O(n!) since, yes, it does scale no worse than n! but it's not particularly helpful information. Big O notation is used imprecisely frequently (see also people saying a dataset is O(millions) to describe scale).
dwohnitmok 4y ago
Big O, Theta, and Omega notations all ultimately denote sets of functions. So e.g. O(n) is the set of all functions which are eventually overtaken by some linear function. When we say "X is O(f(n))" what we really mean is "the function that characterizes X is contained within the set of functions denoted by O(f(n))." Anything that can be described by a function hence can be given Big O, Theta, or Omega notation. So yes worst case time complexity could be described in this notation, but so could average time complexity. But we could also describe things that have nothing to do with time or space complexity with big O notation as well. As long as we've turned it into a function, we can describe it with big O notation.
tsimionescu 4y ago
Worst case, median case, and best case complexity have nothing to do with O/Θ/Ω. When analyzing an algorithm, you want to compute the number of steps it has to execute in certain cases as a function of its input size(s). That function will be something like 2n^2 + 67n + 189 steps. Since this is too much information, you can then express it instead as O(n^2) (or O(n^100)) or Ω(n^2) (or Ω(25n) ) or Θ(n^2). You can then also compute the best case running time of the algorithm as a function of the size of the input, and get 2n^2 + 67n. Then you can say that the best case running time is also O(n^2). Finally, you can (sometimes) define an "average" running time. Now, what do we mean by "shortest running time"? Is that not always for n=0 or something? No - the best case running time has to do with the running time in a case where the input has a certain shape. For some sorting algorithms for example, if the input is already sorted, they will only go through the list once and do nothing, so they have a best case running time that is O(n). Other sorting algorithms will still perform steps even if the input is already sorted, so even their best case running time may be O(n log(n)). Now, you can say that, given any possible input, the running time of the algorithm is O(worse case running time) and Ω(best case running time). You definitely CAN'T say in general that it is Θ(average case running time) though, as in will sometimes run in time that is shorter than "average case running time" (for best case scenarios); or sometimes it will run in time that is longer than "average case running time" (for worse case scenarios). Basically, the worse/best/average case running times are an analysis of how properties other than the size of the input affect its running time. Big-O notation and its friends have nothing to do with complexity analysis. They are a general notation for the asymptotic behavior of mathematical functions. Big-O is usually understood as an upper bound on a function, big-Ω is a lower bound, and Θ is a tight bound (the function f is by definition always within a factor of k above or below Θ(f)). Edit: let's take an example. Say we have the following algorithm: isAllOdd(array x): if x is empty: return true if x[0] is even: return false return isAllOdd(x[1:]) In the best case, for any size array with the first element being even, this function finishes after executing 4 instructions: 2 comparisons, an array access and then a return. So it's best case complexity is best(n) = 4, which is O(1), Θ(1), Ω(1). In the worse case, all elements of the array are odd, so we have to go through all n elements to find that out. It will have to execute 6 instructions for each element in the array (2 comparisons, 2 array accesses, a call and a return), except for the last element where it will execute only 2 instructions (check size then return). So its worst case complexity function is worst(n) = 6(n-1) + 2, which is O(n), Θ(n), Ω(n). In the average case, for every call we are flipping a coin, and we have n total flips. Since we can assume the coin is fair, we will expect to see an even number after log(n/2) calls of isAllOdd. So, our average case complexity is average(n) = 6*log((n-1)/2) + 2 steps, which is O(log n), Θ(log n), Ω(log n). (I am ignoring cases where n < 2, which is anyway irrelevant for asymptotic behavior). Now, what is the overall complexity of isAllOdd? We can generalize the average case calculation if we want to get an exact value; but whatever that function, overall(n), is, we know for sure best(n) < overall(n) < worst(n); so overall(n) is O(n) and Ω(1). However, we can't define any Θ for it - there is no function which it will differ from by at most a constant factor for any n. Why do the detailed analysis instead of saying this is O(n) and being done with it? Well, perhaps we know that we are in fact calling this function with a large number of even numbers, so we would actually over-estimate its complexity. If we instead know we are calling it with a large number of odd numbers, we would also find out from the average case analysis that it would be better to define a reverse funtion, isAllEven, and compute isAllOdd = !isAllEven.
tempnow987 4y ago
I always used big O for worst case (by default). I did think that was common. Theta and Omega I use differently however. I sometimes say, best case if X then it's O(n) or whatever.
throw149102 4y ago
I like to use the metaphor of driving somewhere, and trying to estimate when you're going to get there. Maybe you have a hotel reservation, and you want to make sure you don't get there too early nor too late. Then (with some times filled in for example): +---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+ | . | Best Case (little/no traffic) | Average Case (average traffic) | Worst Case (car accident, snow-in etc) | +---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+ | Max time, upper bound (Big O) | 30 minutes | 45 minutes | 1 hour 20 minutes | | Both min and max, tight bound (Theta) | 25 minutes | 35 minutes | 1 hour | | Minimum time, lower bound (Omega) | 15 minutes | 25 minutes | 50 minutes | +---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+ So then you can start asking questions like - if I assume I'm in the average case, and I can show up earliest at 20 minutes from now, and show up latest at 50 minutes from now, can I guarantee that I will make it within that window? The answer in this case is yes, because our range is 25-45 minutes, so the earliest I can show up is in 25 minutes and the latest in 45 minutes. This also helps explain why Big O is generally more useful - we can almost always be early to something, but we can almost never be late to something. So showing up 5 minutes early usually is not a problem. It also shows why Theta is better than both - in this case, if we had this table we could completely ignore both the Big O row and Omega row, because Theta is a better bound for both min and max time. Of course, in algorithmic complexity we replace the times with functions in terms of some variables, usually just n.
- ahoka 4y ago
  But I have the same table, but instead of time, I have the turns need to be taken by the car. That's not always useful.
- tsimionescu 4y ago
  Your example is nice, but extremely informal, as these are all constant numbers, while O/Theta/Omega (and o, omega, theta) are about functions. I think the most important thing that needs to be clarified though is that algorithmic complexity is first and foremost a function, `WorseCaseComplexity(size of input) = max number of steps for any input of that size`. This function is often then classed into a "complexity class" using O/Theta/Omega etc, but that is only done for the sake of easier comparison of complexities between algorithms.
dudus 4y ago
I remember from college there was big-Oh `O(x)` and little-Oh `o(x)`. Is Omega/Theta the same as little-Oh?
- tsimionescu 4y ago
  No, big O is a kind of loose upper bound, while little-O is a very strict upper bound. f(x) = O(g(x)) <=> there exists k, x0 such that f(x) < k * g(x) for any x > x0 f(x) = o(g(x)) <=> for any k > 0, there exists x0 s.t. f(x) < k * g(x) for any x > x0 For example: f(n) = 3*n^2 + 2n + 1 f(n) = O(n^2)? let's take k = 10 3*n^2 + 2n + 1 < 2 * n^2 for any n > n0? n = 0: 3 * 0^2 + 2*0 + 1 < 10 * 0^2 <=> 1 < 0 false n = 1: 3 * 1^2 + 2*1 + 1 < 10 * 1^2 <=> 6 < 10 true n = 2: 3 * 2^2 + 2*2 + 1 < 10 * 2^2 <=> 17 < 40 true ... so, yes, f(n) = O(n^2) (n0 = 1) f(n) = o(n^2) ? let's take k = 2. 3*n^2 + 2n + 1 < 2 * n^2 for any n > n0? 3 * n^2 + 2 * n + 1 < 2 * n^2 <=> 3 * n^2 + 2 * n + 1 - 2 * n^2 < 0 <=> n^2 + 2 * n + 1 < 0 false for any n > 0. so no, f(n) != o(n^2). However, f(n) = o(10 * n^2), and f(n) = o(n^3). Big-Omega and small-Omega are the same idea for a lower bound. Big-Theta is a tight bound around the function: f(n) = Theta(g(n)) <=> there exists k1, k2, n0 such that k1*g(n) < f(n) < k2*g(n), for any n > n0. There is no equivalent "little-theta", as that would imply that the relation must hold for any k1 and k2, which would at best leave only the function itself as fulfilling the condition.
samhw 4y ago
The other replies are great, but just to put it concisely: big O is ‘worst case’ in terms of input size, while the ‘best case big O’ is ‘best case’ in terms of the input contents (‘shape’).

waynecochran 4y ago

You are mixing two things together. The "average/expected case" and the "worst case" are two different functions, each with their own O, Θ, Ω.

SQueeeeeL 4y ago

You should look into amortized complexity. That's the formalized name for worst case runtime over multiple trials.

bsedlm 4y ago

In my opinion, nothing about big-O and related omega, theta, etc, is at all strict. Maybe I value "pure symbolic clairty" too much. I do see a very pragmatic usefullness to the complexity notation.

larsrc 4y ago

There are variations, that's what we learned back at Uni. Expected O(f(n)), average O(f(n)), amortised O(f(n)), even expected amortised O(f(n)). "Expected" implied a randomised algorithm.

tsimionescu 4y ago
> "Expected" implied a randomised algorithm. Not necessarily. It can be the "expected" number of steps over the range of unknown inputs even for a deterministic algorithm.

vmsp 4y ago

In school, we used big O notation for all cases. I've never heard about theta or omega notation. Wikipedia's bubble sort page -- as an example -- also uses it for all cases. https://en.wikipedia.org/wiki/Bubble_sort https://en.wikipedia.org/wiki/Bubble_sort

rockinghigh 4y ago
You can see the list of notations here: https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann–Landau_notations https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm...

londons_explore 4y ago

Computer scientists stole some notation from mathematicians, but then slightly changed and substantially slackened the definition...

tsimionescu 4y ago
No, not really. CS and other branches of maths are using the exact same definitions of O,o,Θ, and ω. It is true that Ω is used with a different definition in CS, but it's stricter not more slack. As explained elsewhere though, they are not notations for algorithmic complexity, they are notations for function categorization. It just happens that a common use for this notation in CS is to categorize the function "best/average/worse/... case complexity of an algorithm", but they are also used for other purposes.
- ufo 4y ago
  In my experience, a lot of the time when programmers say big O, they actually mean big Theta...
  - adrianN 4y ago
    Programmers need not be very good computer scientists. The actual scientists publishing papers on algorithms usually get it right.
  - tsimionescu 4y ago
    Yes, I agree with that. However, if f(n)=Theta(n) => f(n)=O(n), so they are usually not wrong, technically, just unnecessarily broad.

powersnail 4y ago

I think you are mistaken here. The concept of worst/best/amortized case is different from O/Theta/Omega. The latter is about the direction with which it is bounding. Big O/Theta/Omega denotes sets of functions, and each of them can be applied to best/worst/amortized complexity analysis.

karpierz 4y ago

Theta(X) is not "average case" behaviour, it means "both Omega(X) and O(X)". Ex: merge sort is Theta(n log(n)), but quick sort is not. The author is likely saying "worst case O(n log(n))" as redundancy to emphasize that this is worst case behaviour.

tsimionescu 4y ago
It's not redundant. You can have "average case O(n log(n))" but "worse case O(n^2)", like quicksort does. Depending on the pivot function, that "worse case" can be more or less common.
- karpierz 4y ago
  It is not redundant to say "average case O(n log(n))". It's not formally a correct usage of O(). But colloquially, it means that the average number of operations over all possible inputs on length n is X. It is redundant to say "worst case O(n^2)". By definition, O(X) means that the maximum of the number of operations over all possible inputs of length n is at most X.
  - Kranar 4y ago
    You are incorrect about this. Worst case and Big O are independent of one another. The O, Ω, Θ, etc... are about describing bounds where O(f) is used for the set of asymptotic upper bounds on f, Ω(f) is the set of asymptotic lower bounds on f, and Θ(f) is the intersection of O(f) and Ω(f). Typically f is used to describe space or time complexity of an algorithm, but it can be used for any function that maps positive integers to the non-negative real numbers. You can make any combination of best case/worst case/average case with O, Ω, Θ. In fact, you can even consider other cases as well such as amortized cases, 90th percentile cases, any case you want to investigate that can be defined as a function from positive integers to non-negative real numbers can be classified as having an asymptotic upper bound, lower bound, or tight bound.
    - karpierz 4y ago

Corence 4y ago

O, Theta, and Omega are independent from best, worst, and average case. You can mathematically establish upper, lower, or exact bounds on any of the average, best, or worst cases. It is perfectly valid to say "the best case is O(n)" which means the best case scales no worse than linearly. The "no worse" here is not describing the best case, but rather the strictness of your bound. You could say a sort algorithm is O(n!) since, yes, it does scale no worse than n! but it's not particularly helpful information. Big O notation is used imprecisely frequently (see also people saying a dataset is O(millions) to describe scale).

dwohnitmok 4y ago

Big O, Theta, and Omega notations all ultimately denote sets of functions. So e.g. O(n) is the set of all functions which are eventually overtaken by some linear function. When we say "X is O(f(n))" what we really mean is "the function that characterizes X is contained within the set of functions denoted by O(f(n))." Anything that can be described by a function hence can be given Big O, Theta, or Omega notation. So yes worst case time complexity could be described in this notation, but so could average time complexity. But we could also describe things that have nothing to do with time or space complexity with big O notation as well. As long as we've turned it into a function, we can describe it with big O notation.

tsimionescu 4y ago

Worst case, median case, and best case complexity have nothing to do with O/Θ/Ω. When analyzing an algorithm, you want to compute the number of steps it has to execute in certain cases as a function of its input size(s). That function will be something like 2n^2 + 67n + 189 steps. Since this is too much information, you can then express it instead as O(n^2) (or O(n^100)) or Ω(n^2) (or Ω(25n) ) or Θ(n^2). You can then also compute the best case running time of the algorithm as a function of the size of the input, and get 2n^2 + 67n. Then you can say that the best case running time is also O(n^2). Finally, you can (sometimes) define an "average" running time. Now, what do we mean by "shortest running time"? Is that not always for n=0 or something? No - the best case running time has to do with the running time in a case where the input has a certain shape. For some sorting algorithms for example, if the input is already sorted, they will only go through the list once and do nothing, so they have a best case running time that is O(n). Other sorting algorithms will still perform steps even if the input is already sorted, so even their best case running time may be O(n log(n)). Now, you can say that, given any possible input, the running time of the algorithm is O(worse case running time) and Ω(best case running time). You definitely CAN'T say in general that it is Θ(average case running time) though, as in will sometimes run in time that is shorter than "average case running time" (for best case scenarios); or sometimes it will run in time that is longer than "average case running time" (for worse case scenarios). Basically, the worse/best/average case running times are an analysis of how properties other than the size of the input affect its running time. Big-O notation and its friends have nothing to do with complexity analysis. They are a general notation for the asymptotic behavior of mathematical functions. Big-O is usually understood as an upper bound on a function, big-Ω is a lower bound, and Θ is a tight bound (the function f is by definition always within a factor of k above or below Θ(f)). Edit: let's take an example. Say we have the following algorithm: isAllOdd(array x): if x is empty: return true if x[0] is even: return false return isAllOdd(x[1:]) In the best case, for any size array with the first element being even, this function finishes after executing 4 instructions: 2 comparisons, an array access and then a return. So it's best case complexity is best(n) = 4, which is O(1), Θ(1), Ω(1). In the worse case, all elements of the array are odd, so we have to go through all n elements to find that out. It will have to execute 6 instructions for each element in the array (2 comparisons, 2 array accesses, a call and a return), except for the last element where it will execute only 2 instructions (check size then return). So its worst case complexity function is worst(n) = 6(n-1) + 2, which is O(n), Θ(n), Ω(n). In the average case, for every call we are flipping a coin, and we have n total flips. Since we can assume the coin is fair, we will expect to see an even number after log(n/2) calls of isAllOdd. So, our average case complexity is average(n) = 6*log((n-1)/2) + 2 steps, which is O(log n), Θ(log n), Ω(log n). (I am ignoring cases where n < 2, which is anyway irrelevant for asymptotic behavior). Now, what is the overall complexity of isAllOdd? We can generalize the average case calculation if we want to get an exact value; but whatever that function, overall(n), is, we know for sure best(n) < overall(n) < worst(n); so overall(n) is O(n) and Ω(1). However, we can't define any Θ for it - there is no function which it will differ from by at most a constant factor for any n. Why do the detailed analysis instead of saying this is O(n) and being done with it? Well, perhaps we know that we are in fact calling this function with a large number of even numbers, so we would actually over-estimate its complexity. If we instead know we are calling it with a large number of odd numbers, we would also find out from the average case analysis that it would be better to define a reverse funtion, isAllEven, and compute isAllOdd = !isAllEven.

tempnow987 4y ago

I always used big O for worst case (by default). I did think that was common. Theta and Omega I use differently however. I sometimes say, best case if X then it's O(n) or whatever.

throw149102 4y ago

I like to use the metaphor of driving somewhere, and trying to estimate when you're going to get there. Maybe you have a hotel reservation, and you want to make sure you don't get there too early nor too late. Then (with some times filled in for example): +---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+ | . | Best Case (little/no traffic) | Average Case (average traffic) | Worst Case (car accident, snow-in etc) | +---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+ | Max time, upper bound (Big O) | 30 minutes | 45 minutes | 1 hour 20 minutes | | Both min and max, tight bound (Theta) | 25 minutes | 35 minutes | 1 hour | | Minimum time, lower bound (Omega) | 15 minutes | 25 minutes | 50 minutes | +---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+ So then you can start asking questions like - if I assume I'm in the average case, and I can show up earliest at 20 minutes from now, and show up latest at 50 minutes from now, can I guarantee that I will make it within that window? The answer in this case is yes, because our range is 25-45 minutes, so the earliest I can show up is in 25 minutes and the latest in 45 minutes. This also helps explain why Big O is generally more useful - we can almost always be early to something, but we can almost never be late to something. So showing up 5 minutes early usually is not a problem. It also shows why Theta is better than both - in this case, if we had this table we could completely ignore both the Big O row and Omega row, because Theta is a better bound for both min and max time. Of course, in algorithmic complexity we replace the times with functions in terms of some variables, usually just n.

ahoka 4y ago
But I have the same table, but instead of time, I have the turns need to be taken by the car. That's not always useful.
tsimionescu 4y ago
Your example is nice, but extremely informal, as these are all constant numbers, while O/Theta/Omega (and o, omega, theta) are about functions. I think the most important thing that needs to be clarified though is that algorithmic complexity is first and foremost a function, `WorseCaseComplexity(size of input) = max number of steps for any input of that size`. This function is often then classed into a "complexity class" using O/Theta/Omega etc, but that is only done for the sake of easier comparison of complexities between algorithms.

dudus 4y ago

I remember from college there was big-Oh `O(x)` and little-Oh `o(x)`. Is Omega/Theta the same as little-Oh?

tsimionescu 4y ago
No, big O is a kind of loose upper bound, while little-O is a very strict upper bound. f(x) = O(g(x)) <=> there exists k, x0 such that f(x) < k * g(x) for any x > x0 f(x) = o(g(x)) <=> for any k > 0, there exists x0 s.t. f(x) < k * g(x) for any x > x0 For example: f(n) = 3*n^2 + 2n + 1 f(n) = O(n^2)? let's take k = 10 3*n^2 + 2n + 1 < 2 * n^2 for any n > n0? n = 0: 3 * 0^2 + 2*0 + 1 < 10 * 0^2 <=> 1 < 0 false n = 1: 3 * 1^2 + 2*1 + 1 < 10 * 1^2 <=> 6 < 10 true n = 2: 3 * 2^2 + 2*2 + 1 < 10 * 2^2 <=> 17 < 40 true ... so, yes, f(n) = O(n^2) (n0 = 1) f(n) = o(n^2) ? let's take k = 2. 3*n^2 + 2n + 1 < 2 * n^2 for any n > n0? 3 * n^2 + 2 * n + 1 < 2 * n^2 <=> 3 * n^2 + 2 * n + 1 - 2 * n^2 < 0 <=> n^2 + 2 * n + 1 < 0 false for any n > 0. so no, f(n) != o(n^2). However, f(n) = o(10 * n^2), and f(n) = o(n^3). Big-Omega and small-Omega are the same idea for a lower bound. Big-Theta is a tight bound around the function: f(n) = Theta(g(n)) <=> there exists k1, k2, n0 such that k1*g(n) < f(n) < k2*g(n), for any n > n0. There is no equivalent "little-theta", as that would imply that the relation must hold for any k1 and k2, which would at best leave only the function itself as fulfilling the condition.

samhw 4y ago

The other replies are great, but just to put it concisely: big O is ‘worst case’ in terms of input size, while the ‘best case big O’ is ‘best case’ in terms of the input contents (‘shape’).