914

Most people with a degree in CS will certainly know what Big O stands for. It helps us to measure how well an algorithm scales.

But I'm curious, how do *you* calculate or approximate the complexity of your algorithms?

This question is tagged with
`algorithm`

`optimization`

`complexity-theory`

`big-o`

`performance`

~ Asked on 2008-08-06 10:18:16

1501

I'll do my best to explain it here on simple terms, but be warned that this topic takes my students a couple of months to finally grasp. You can find more information on the Chapter 2 of the Data Structures and Algorithms in Java book.

There is no mechanical procedure that can be used to get the BigOh.

As a "cookbook", to obtain the BigOh from a piece of code you first need to realize that you are creating a math formula to count how many steps of computations get executed given an input of some size.

The purpose is simple: to compare algorithms from a theoretical point of view, without the need to execute the code. The lesser the number of steps, the faster the algorithm.

For example, let's say you have this piece of code:

```
int sum(int* data, int N) {
int result = 0; // 1
for (int i = 0; i < N; i++) { // 2
result += data[i]; // 3
}
return result; // 4
}
```

This function returns the sum of all the elements of the array, and we want to create a formula to count the computational complexity of that function:

```
Number_Of_Steps = f(N)
```

So we have `f(N)`

, a function to count the number of computational steps. The input of the function is the size of the structure to process. It means that this function is called such as:

```
Number_Of_Steps = f(data.length)
```

The parameter `N`

takes the `data.length`

value. Now we need the actual definition of the function `f()`

. This is done from the source code, in which each interesting line is numbered from 1 to 4.

There are many ways to calculate the BigOh. From this point forward we are going to assume that every sentence that doesn't depend on the size of the input data takes a constant `C`

number computational steps.

We are going to add the individual number of steps of the function, and neither the local variable declaration nor the return statement depends on the size of the `data`

array.

That means that lines 1 and 4 takes C amount of steps each, and the function is somewhat like this:

```
f(N) = C + ??? + C
```

The next part is to define the value of the `for`

statement. Remember that we are counting the number of computational steps, meaning that the body of the `for`

statement gets executed `N`

times. That's the same as adding `C`

, `N`

times:

```
f(N) = C + (C + C + ... + C) + C = C + N * C + C
```

There is no mechanical rule to count how many times the body of the `for`

gets executed, you need to count it by looking at what does the code do. To simplify the calculations, we are ignoring the variable initialization, condition and increment parts of the `for`

statement.

To get the actual BigOh we need the Asymptotic analysis of the function. This is roughly done like this:

- Take away all the constants
`C`

. - From
`f()`

get the polynomium in its`standard form`

. - Divide the terms of the polynomium and sort them by the rate of growth.
- Keep the one that grows bigger when
`N`

approaches`infinity`

.

Our `f()`

has two terms:

```
f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1
```

Taking away all the `C`

constants and redundant parts:

```
f(N) = 1 + N ^ 1
```

Since the last term is the one which grows bigger when `f()`

approaches infinity (think on limits) this is the BigOh argument, and the `sum()`

function has a BigOh of:

```
O(N)
```

There are a few tricks to solve some tricky ones: use summations whenever you can.

As an example, this code can be easily solved using summations:

```
for (i = 0; i < 2*n; i += 2) { // 1
for (j=n; j > i; j--) { // 2
foo(); // 3
}
}
```

The first thing you needed to be asked is the order of execution of `foo()`

. While the usual is to be `O(1)`

, you need to ask your professors about it. `O(1)`

means (almost, mostly) constant `C`

, independent of the size `N`

.

The `for`

statement on the sentence number one is tricky. While the index ends at `2 * N`

, the increment is done by two. That means that the first `for`

gets executed only `N`

steps, and we need to divide the count by two.

```
f(N) = Summation(i from 1 to 2 * N / 2)( ... ) =
= Summation(i from 1 to N)( ... )
```

The sentence number *two* is even trickier since it depends on the value of `i`

. Take a look: the index i takes the values: 0, 2, 4, 6, 8, ..., 2 * N, and the second `for`

get executed: N times the first one, N - 2 the second, N - 4 the third... up to the N / 2 stage, on which the second `for`

never gets executed.

On formula, that means:

```
f(N) = Summation(i from 1 to N)( Summation(j = ???)( ) )
```

Again, we are counting **the number of steps**. And by definition, every summation should always start at one, and end at a number bigger-or-equal than one.

```
f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )
```

(We are assuming that `foo()`

is `O(1)`

and takes `C`

steps.)

We have a problem here: when `i`

takes the value `N / 2 + 1`

upwards, the inner Summation ends at a negative number! That's impossible and wrong. We need to split the summation in two, being the pivotal point the moment `i`

takes `N / 2 + 1`

.

```
f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )
```

Since the pivotal moment `i > N / 2`

, the inner `for`

won't get executed, and we are assuming a constant C execution complexity on its body.

Now the summations can be simplified using some identity rules:

- Summation(w from 1 to N)( C ) = N * C
- Summation(w from 1 to N)( A (+/-) B ) = Summation(w from 1 to N)( A ) (+/-) Summation(w from 1 to N)( B )
- Summation(w from 1 to N)( w * C ) = C * Summation(w from 1 to N)( w ) (C is a constant, independent of
`w`

) - Summation(w from 1 to N)( w ) = (N * (N + 1)) / 2

Applying some algebra:

```
f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )
f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )
=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )
=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 =
(N / 2 - 1) * (N / 2) / 2 =
((N ^ 2 / 4) - (N / 2)) / 2 =
(N ^ 2 / 8) - (N / 4)
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )
f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + C * N
f(N) = C * 1/4 * N ^ 2 + C * N
```

And the BigOh is:

```
O(N²)
```

~ Answered on 2011-01-31 15:33:54

205

Big O gives the upper bound for time complexity of an algorithm. It is usually used in conjunction with processing data sets (lists) but can be used elsewhere.

A few examples of how it's used in C code.

Say we have an array of n elements

```
int array[n];
```

If we wanted to access the first element of the array this would be O(1) since it doesn't matter how big the array is, it always takes the same constant time to get the first item.

```
x = array[0];
```

If we wanted to find a number in the list:

```
for(int i = 0; i < n; i++){
if(array[i] == numToFind){ return i; }
}
```

This would be O(n) since at most we would have to look through the entire list to find our number. The Big-O is still O(n) even though we might find our number the first try and run through the loop once because Big-O describes the upper bound for an algorithm (omega is for lower bound and theta is for tight bound).

When we get to nested loops:

```
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
array[j] += 2;
}
}
```

This is O(n^2) since for each pass of the outer loop ( O(n) ) we have to go through the entire list again so the n's multiply leaving us with n squared.

This is barely scratching the surface but when you get to analyzing more complex algorithms complex math involving proofs comes into play. Hope this familiarizes you with the basics at least though.

~ Answered on 2008-08-06 13:34:13

97

While knowing how to figure out the Big O time for your particular problem is useful, knowing some general cases can go a long way in helping you make decisions in your algorithm.

Here are some of the most common cases, lifted from http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O(1) - Determining if a number is even or odd; using a constant-size lookup table or hash table

O(logn) - Finding an item in a sorted array with a binary search

O(n) - Finding an item in an unsorted list; adding two n-digit numbers

O(n^{2}) - Multiplying two n-digit numbers by a simple algorithm; adding two n×n matrices; bubble sort or insertion sort

O(n^{3}) - Multiplying two n×n matrices by simple algorithm

O(c^{n}) - Finding the (exact) solution to the traveling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute force

O(n!) - Solving the traveling salesman problem via brute-force search

O(n^{n}) - Often used instead of O(n!) to derive simpler formulas for asymptotic complexity

~ Answered on 2008-09-05 19:09:48

43

Small reminder: the `big O`

notation is used to denote *asymptotic* complexity (that is, when the size of the problem grows to infinity), *and* it hides a constant.

This means that between an algorithm in O(n) and one in O(n^{2}), the fastest is not always the first one (though there always exists a value of n such that for problems of size >n, the first algorithm is the fastest).

Note that the hidden constant very much depends on the implementation!

Also, in some cases, the runtime is not a deterministic function of the *size* n of the input. Take sorting using quick sort for example: the time needed to sort an array of n elements is not a constant but depends on the starting configuration of the array.

There are different time complexities:

- Worst case (usually the simplest to figure out, though not always very meaningful)
Average case (usually much harder to figure out...)

...

A good introduction is *An Introduction to the Analysis of Algorithms* by R. Sedgewick and P. Flajolet.

As you say, `premature optimisation is the root of all evil`

, and (if possible) *profiling* really should always be used when optimising code. It can even help you determine the complexity of your algorithms.

~ Answered on 2008-08-23 20:43:50

30

Seeing the answers here I think we can conclude that most of us do indeed approximate the order of the algorithm by *looking* at it and use common sense instead of calculating it with, for example, the master method as we were thought at university.
With that said I must add that even the professor encouraged us (later on) to actually *think* about it instead of just calculating it.

Also I would like to add how it is done for **recursive functions**:

suppose we have a function like (scheme code):

```
(define (fac n)
(if (= n 0)
1
(* n (fac (- n 1)))))
```

which recursively calculates the factorial of the given number.

The first step is to try and determine the performance characteristic for *the body of the function only* in this case, nothing special is done in the body, just a multiplication (or the return of the value 1).

So the **performance for the body is: O(1)** (constant).

Next try and determine this for the *number of recursive calls*. In this case we have n-1 recursive calls.

So the **performance for the recursive calls is: O(n-1)** (order is n, as we throw away the insignificant parts).

Then put those two together and you then have the performance for the whole recursive function:

**1 * (n-1) = O(n)**

Peter, to answer your raised issues; the method I describe here actually handles this quite well. But keep in mind that this is still an *approximation* and not a full mathematically correct answer. The method described here is also one of the methods we were taught at university, and if I remember correctly was used for far more advanced algorithms than the factorial I used in this example.

Of course it all depends on how well you can estimate the running time of the body of the function and the number of recursive calls, but that is just as true for the other methods.

~ Answered on 2008-08-07 08:10:04

27

If your cost is a polynomial, just keep the highest-order term, without its multiplier. E.g.:

O((n/2 + 1)*(n/2)) = O(n

^{2}/4 + n/2) = O(n^{2}/4) = O(n^{2})

This doesn't work for infinite series, mind you. There is no single recipe for the general case, though for some common cases, the following inequalities apply:

O(log

N) < O(N) < O(NlogN) < O(N^{2}) < O(N^{k}) < O(e^{n}) < O(n!)

~ Answered on 2011-01-31 13:30:15

22

Lets start from the beginning.

First of all, accept the principle that certain simple operations on data can be done in `O(1)`

time, that is, in time that is independent of the size of the input. These primitive operations in C consist of

- Arithmetic operations (e.g. + or %).
- Logical operations (e.g., &&).
- Comparison operations (e.g., <=).
- Structure accessing operations (e.g. array-indexing like A[i], or pointer fol- lowing with the -> operator).
- Simple assignment such as copying a value into a variable.
- Calls to library functions (e.g., scanf, printf).

The justification for this principle requires a detailed study of the machine instructions (primitive steps) of a typical computer. Each of the described operations can be done with some small number of machine instructions; often only one or two instructions are needed.
As a consequence, several kinds of statements in C can be executed in `O(1)`

time, that is, in some constant amount of time independent of input. These simple include

- Assignment statements that do not involve function calls in their expressions.
- Read statements.
- Write statements that do not require function calls to evaluate arguments.
- The jump statements break, continue, goto, and return expression, where expression does not contain a function call.

In C, many for-loops are formed by initializing an index variable to some value and incrementing that variable by 1 each time around the loop. The for-loop ends when the index reaches some limit. For instance, the for-loop

```
for (i = 0; i < n-1; i++)
{
small = i;
for (j = i+1; j < n; j++)
if (A[j] < A[small])
small = j;
temp = A[small];
A[small] = A[i];
A[i] = temp;
}
```

uses index variable i. It increments i by 1 each time around the loop, and the iterations stop when i reaches n - 1.

However, for the moment, focus on the simple form of for-loop, where the **difference between the final and initial values, divided by the amount by which the index variable is incremented tells us how many times we go around the loop**. That count is exact, unless there are ways to exit the loop via a jump statement; it is an upper bound on the number of iterations in any case.

For instance, the for-loop iterates `((n - 1) - 0)/1 = n - 1 times`

,
since 0 is the initial value of i, n - 1 is the highest value reached by i (i.e., when i
reaches n-1, the loop stops and no iteration occurs with i = n-1), and 1 is added
to i at each iteration of the loop.

In the simplest case, where the time spent in the loop body is the same for each
iteration, **we can multiply the big-oh upper bound for the body by the number of
times around the loop**. Strictly speaking, we must then **add O(1) time to initialize
the loop index and O(1) time for the first comparison of the loop index with the
limit**, because we test one more time than we go around the loop. However, unless
it is possible to execute the loop zero times, the time to initialize the loop and test
the limit once is a low-order term that can be dropped by the summation rule.

Now consider this example:

```
(1) for (j = 0; j < n; j++)
(2) A[i][j] = 0;
```

We know that **line (1)** takes `O(1)`

time. Clearly, we go around the loop n times, as
we can determine by subtracting the lower limit from the upper limit found on line
(1) and then adding 1. Since the body, line (2), takes O(1) time, we can neglect the
time to increment j and the time to compare j with n, both of which are also O(1).
Thus, the running time of lines (1) and (2) is the **product of n and O(1)**, which is `O(n)`

.

Similarly, we can bound the running time of the outer loop consisting of lines (2) through (4), which is

```
(2) for (i = 0; i < n; i++)
(3) for (j = 0; j < n; j++)
(4) A[i][j] = 0;
```

We have already established that the loop of lines (3) and (4) takes O(n) time. Thus, we can neglect the O(1) time to increment i and to test whether i < n in each iteration, concluding that each iteration of the outer loop takes O(n) time.

The initialization i = 0 of the outer loop and the (n + 1)st test of the condition
i < n likewise take O(1) time and can be neglected. Finally, we observe that we go
around the outer loop n times, taking O(n) time for each iteration, giving a total
`O(n^2)`

running time.

A more practical example.

~ Answered on 2014-02-02 15:30:25

22

I think about it in terms of information. Any problem consists of learning a certain number of bits.

Your basic tool is the concept of decision points and their entropy. The entropy of a decision point is the average information it will give you. For example, if a program contains a decision point with two branches, it's entropy is the sum of the probability of each branch times the log_{2} of the inverse probability of that branch. That's how much you learn by executing that decision.

For example, an `if`

statement having two branches, both equally likely, has an entropy of 1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1. So its entropy is 1 bit.

Suppose you are searching a table of N items, like N=1024. That is a 10-bit problem because log(1024) = 10 bits. So if you can search it with IF statements that have equally likely outcomes, it should take 10 decisions.

That's what you get with binary search.

Suppose you are doing linear search. You look at the first element and ask if it's the one you want. The probabilities are 1/1024 that it is, and 1023/1024 that it isn't. The entropy of that decision is 1/1024*log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024 * 10 + 1023/1024 * about 0 = about .01 bit. You've learned very little! The second decision isn't much better. That is why linear search is so slow. In fact it's exponential in the number of bits you need to learn.

Suppose you are doing indexing. Suppose the table is pre-sorted into a lot of bins, and you use some of all of the bits in the key to index directly to the table entry. If there are 1024 bins, the entropy is 1/1024 * log(1024) + 1/1024 * log(1024) + ... for all 1024 possible outcomes. This is 1/1024 * 10 times 1024 outcomes, or 10 bits of entropy for that one indexing operation. That is why indexing search is fast.

Now think about sorting. You have N items, and you have a list. For each item, you have to search for where the item goes in the list, and then add it to the list. So sorting takes roughly N times the number of steps of the underlying search.

So sorts based on binary decisions having roughly equally likely outcomes all take about O(N log N) steps. An O(N) sort algorithm is possible if it is based on indexing search.

I've found that nearly all algorithmic performance issues can be looked at in this way.

~ Answered on 2009-03-10 13:24:13

14

If you want to estimate the order of your code empirically rather than by analyzing the code, you could stick in a series of increasing values of n and time your code. Plot your timings on a log scale. If the code is O(x^n), the values should fall on a line of slope n.

This has several advantages over just studying the code. For one thing, you can see whether you're in the range where the run time approaches its asymptotic order. Also, you may find that some code that you thought was order O(x) is really order O(x^2), for example, because of time spent in library calls.

~ Answered on 2008-12-11 20:49:05

11

Basically the thing that crops up 90% of the time is just analyzing loops. Do you have single, double, triple nested loops? The you have O(n), O(n^2), O(n^3) running time.

Very rarely (unless you are writing a platform with an extensive base library (like for instance, the .NET BCL, or C++'s STL) you will encounter anything that is more difficult than just looking at your loops (for statements, while, goto, etc...)

~ Answered on 2008-08-14 15:35:50

8

Big O notation is useful because it's easy to work with and hides unnecessary complications and details (for some definition of unnecessary). One nice way of working out the complexity of divide and conquer algorithms is the tree method. Let's say you have a version of quicksort with the median procedure, so you split the array into perfectly balanced subarrays every time.

Now build a tree corresponding to all the arrays you work with. At the root you have the original array, the root has two children which are the subarrays. Repeat this until you have single element arrays at the bottom.

Since we can find the median in O(n) time and split the array in two parts in O(n) time, the work done at each node is O(k) where k is the size of the array. Each level of the tree contains (at most) the entire array so the work per level is O(n) (the sizes of the subarrays add up to n, and since we have O(k) per level we can add this up). There are only log(n) levels in the tree since each time we halve the input.

Therefore we can upper bound the amount of work by O(n*log(n)).

However, Big O hides some details which we sometimes can't ignore. Consider computing the Fibonacci sequence with

```
a=0;
b=1;
for (i = 0; i <n; i++) {
tmp = b;
b = a + b;
a = tmp;
}
```

and lets just assume the a and b are BigIntegers in Java or something that can handle arbitrarily large numbers. Most people would say this is an O(n) algorithm without flinching. The reasoning is that you have n iterations in the for loop and O(1) work in side the loop.

But Fibonacci numbers are large, the n-th Fibonacci number is exponential in n so just storing it will take on the order of n bytes. Performing addition with big integers will take O(n) amount of work. So the total amount of work done in this procedure is

1 + 2 + 3 + ... + n = n(n-1)/2 = O(n^2)

So this algorithm runs in quadradic time!

~ Answered on 2008-08-08 13:53:20

8

Less useful generally, I think, but for the sake of completeness there is also a Big Omega O, which defines a lower-bound on an algorithm's complexity, and a Big Theta T, which defines both an upper and lower bound.

~ Answered on 2008-09-23 07:26:08

7

Familiarity with the algorithms/data structures I use and/or quick glance analysis of iteration nesting. The difficulty is when you call a library function, possibly multiple times - you can often be unsure of whether you are calling the function unnecessarily at times or what implementation they are using. Maybe library functions should have a complexity/efficiency measure, whether that be Big O or some other metric, that is available in documentation or even IntelliSense.

~ Answered on 2008-08-06 10:59:40

7

Break down the algorithm into pieces you know the big O notation for, and combine through big O operators. That's the only way I know of.

For more information, check the Wikipedia page on the subject.

~ Answered on 2008-08-06 11:34:26

6

As to "how do you calculate" Big O, this is part of Computational complexity theory. For some (many) special cases you may be able to come with some simple heuristics (like multiplying loop counts for nested loops), esp. when all you want is any upper bound estimation, and you do not mind if it is too pessimistic - which I guess is probably what your question is about.

If you really want to answer your question for any algorithm the best you can do is to apply the theory. Besides of simplistic "worst case" analysis I have found Amortized analysis very useful in practice.

~ Answered on 2009-03-10 15:02:13

6

For the 1st case, the inner loop is executed `n-i`

times, so the total number of executions is the sum for `i`

going from `0`

to `n-1`

(because lower than, not lower than or equal) of the `n-i`

. You get finally `n*(n + 1) / 2`

, so `O(n²/2) = O(n²)`

.

For the 2nd loop, `i`

is between `0`

and `n`

included for the outer loop; then the inner loop is executed when `j`

is strictly greater than `n`

, which is then impossible.

~ Answered on 2011-01-31 14:36:02

5

Don't forget to also allow for space complexities that can also be a cause for concern if one has limited memory resources. So for example you may hear someone wanting a constant space algorithm which is basically a way of saying that the amount of space taken by the algorithm doesn't depend on any factors inside the code.

Sometimes the complexity can come from how many times is something called, how often is a loop executed, how often is memory allocated, and so on is another part to answer this question.

Lastly, big O can be used for worst case, best case, and amortization cases where generally it is the worst case that is used for describing how bad an algorithm may be.

~ Answered on 2008-10-14 20:16:38

5

In addition to using the master method (or one of its specializations), I test my algorithms experimentally. This can't *prove* that any particular complexity class is achieved, but it can provide reassurance that the mathematical analysis is appropriate. To help with this reassurance, I use code coverage tools in conjunction with my experiments, to ensure that I'm exercising all the cases.

As a very simple example say you wanted to do a sanity check on the speed of the .NET framework's list sort. You could write something like the following, then analyze the results in Excel to make sure they did not exceed an n*log(n) curve.

In this example I measure the number of comparisons, but it's also prudent to examine the actual time required for each sample size. However then you must be even more careful that you are just measuring the algorithm and not including artifacts from your test infrastructure.

```
int nCmp = 0;
System.Random rnd = new System.Random();
// measure the time required to sort a list of n integers
void DoTest(int n)
{
List<int> lst = new List<int>(n);
for( int i=0; i<n; i++ )
lst[i] = rnd.Next(0,1000);
// as we sort, keep track of the number of comparisons performed!
nCmp = 0;
lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }
System.Console.Writeline( "{0},{1}", n, nCmp );
}
// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
DoTest(n);
```

~ Answered on 2008-09-05 18:33:32

4

great question!

**Disclaimer: this answer contains false statements see the comments below.**

If you're using the Big O, you're talking about the worse case (more on what that means later). Additionally, there is capital theta for average case and a big omega for best case.

Check out this site for a lovely formal definition of Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) means there are positive constants c and k, such that 0 = f(n) = cg(n) for all n = k. The values of c and k must be fixed for the function f and must not depend on n.

Ok, so now what do we mean by "best-case" and "worst-case" complexities?

This is probably most clearly illustrated through examples. For example if we are using linear search to find a number in a sorted array then the **worst case** is when we decide to **search for the last element** of the array as this would take as many steps as there are items in the array. The **best case** would be when we search for the **first element** since we would be done after the first check.

The point of all these *adjective*-case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with *multiple* functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.

Sorry this is so poorly written and lacks much technical information. But hopefully it'll make time complexity classes easier to think about. Once you become comfortable with these it becomes a simple matter of parsing through your program and looking for things like for-loops that depend on array sizes and reasoning based on your data structures what kind of input would result in trivial cases and what input would result in worst-cases.

~ Answered on 2016-08-20 04:57:30

4

What often gets overlooked is the *expected* behavior of your algorithms. **It doesn't change the Big-O of your algorithm**, but it does relate to the statement "premature optimization. . .."

Expected behavior of your algorithm is -- very dumbed down -- how fast you can expect your algorithm to work on data you're most likely to see.

For instance, if you're searching for a value in a list, it's O(n), but if you know that most lists you see have your value up front, typical behavior of your algorithm is faster.

To really nail it down, you need to be able to describe the probability distribution of your "input space" (if you need to sort a list, how often is that list already going to be sorted? how often is it totally reversed? how often is it mostly sorted?) It's not always feasible that you know that, but sometimes you do.

~ Answered on 2009-03-10 14:30:13

2

I would like to explain the Big-O in a little bit different aspect.

Big-O is just to compare the complexity of the programs which means how fast are they growing when the inputs are increasing and not the exact time which is spend to do the action.

IMHO in the big-O formulas you better not to use more complex equations (you might just stick to the ones in the following graph.) However you still might use other more precise formula (like 3^n, n^3, ...) but more than that can be sometimes misleading! So better to keep it as simple as possible.

I would like to emphasize once again that here we don't want to get an exact formula for our algorithm. We only want to show how it grows when the inputs are growing and compare with the other algorithms in that sense. Otherwise you would better use different methods like bench-marking.

~ Answered on 2019-02-20 10:44:36

2

I don't know how to programmatically solve this, but the first thing people do is that we sample the algorithm for certain patterns in the number of operations done, say 4n^2 + 2n + 1 we have 2 rules:

- If we have a sum of terms, the term with the largest growth rate is kept, with other terms omitted.
- If we have a product of several factors constant factors are omitted.

If we simplify f(x), where f(x) is the formula for number of operations done, (4n^2 + 2n + 1 explained above), we obtain the big-O value [O(n^2) in this case]. But this would have to account for Lagrange interpolation in the program, which may be hard to implement. And what if the real big-O value was O(2^n), and we might have something like O(x^n), so this algorithm probably wouldn't be programmable. But if someone proves me wrong, give me the code . . . .

~ Answered on 2013-05-11 01:32:45

2

For code A, the outer loop will execute for `n+1`

times, the '1' time means the process which checks the whether i still meets the requirement. And inner loop runs `n`

times, `n-2`

times.... Thus,`0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)`

.

For code B, though inner loop wouldn't step in and execute the foo(), the inner loop will be executed for n times depend on outer loop execution time, which is O(n)

~ Answered on 2011-01-31 20:07:35

- Why are my PowerShell scripts not running?
- Checking if a list is empty with LINQ
- How do you create optional arguments in php?
- Truncate (not round) decimal places in SQL Server
- Any way to write a Windows .bat file to kill processes?
- What is the best free memory leak detector for a C/C++ program and its plug-in DLLs?
- How do I export (and then import) a Subversion repository?
- Storing a file in a database as opposed to the file system?
- Difference between the Apache HTTP Server and Apache Tomcat?
- How to get the last day of the month?
- What are some resources for getting started in operating system development?
- Learning to write a compiler
- How do I create a foreign key in SQL Server?
- Storing Images in DB - Yea or Nay?
- Struct like objects in Java
- What does the [Flags] Enum Attribute mean in C#?
- What is Turing Complete?
- Database, Table and Column Naming Conventions?
- Difference between EXISTS and IN in SQL?
- How to download a file over HTTP?
- Are the shift operators (<<, >>) arithmetic or logical in C?
- How do you list all triggers in a MySQL database?
- How do you pass a function as a parameter in C?
- Quick easy way to migrate SQLite3 to MySQL?
- What are some good SSH Servers for windows?
- JavaScript editor within Eclipse
- How do I use itertools.groupby()?
- Get month and year from a datetime in SQL Server 2005
- Delete all but the most recent X files in bash
- Generator expressions vs. list comprehensions
- When do you use POST and when do you use GET?
- What is the difference between an int and an Integer in Java and C#?
- Explicit vs implicit SQL joins
- How do I change the number of open files limit in Linux?
- Is there a constraint that restricts my generic method to numeric types?
- How can a Java program get its own process ID?
- Recommended Fonts for Programming?
- How do I get the full url of the page I am on in C#
- The imported project "C:\Microsoft.CSharp.targets" was not found
- How do you kill all current connections to a SQL Server 2005 database?
- How do I remove duplicates from a C# array?
- How exactly do you configure httpOnlyCookies in ASP.NET?
- How to convert std::string to LPCWSTR in C++ (Unicode)
- Copy/duplicate database without using mysqldump
- How can I determine whether a specific file is open in Windows?
- How do I create a branch?
- Can someone explain __all__ in Python?
- How do you create a foreign key relationship in a SQL Server CE (Compact Edition) Database?
- Getting ssh to execute a command in the background on target machine
- Log4Net configuring log level
- Accessing a Dictionary.Keys Key through a numeric index
- What is the argument for printf that formats a long?
- How do you sort a dictionary by value?
- In C++, what is a virtual base class?
- How do I use 3DES encryption/decryption in Java?
- How to pass a single object[] to a params object[]
- How does database indexing work?
- How to check for file lock?
- How do I split a string so I can access item x?
- How do I get today's date in C# in mm/dd/yyyy format?
- List of macOS text editors and code editors
- String literals and escape characters in postgresql
- Best way to access a control on another form in Windows Forms?
- Algorithm to find Largest prime factor of a number
- SQL Group By with an Order By
- php execute a background process
- How do you debug PHP scripts?
- Best programming based games
- Make browser window blink in task Bar
- What is a mutex?
- How can I remove duplicate rows?
- Cleanest Way to Invoke Cross-Thread Events
- SQL Server: Get data for only the past year
- Multiple submit buttons in an HTML form
- How do I determine the size of my array in C?
- How do I list loaded plugins in Vim?
- Most efficient way to concatenate strings?
- Versioning SQL Server database
- Differences between MySQL and SQL Server
- Image UriSource and Data Binding
- Calling a function of a module by using its name (a string)
- How to deal with "java.lang.OutOfMemoryError: Java heap space" error?
- How to validate an email address in JavaScript
- How do I retrieve my MySQL username and password?
- How to resolve symbolic links in a shell script
- Getting the ID of the element that fired an event
- Possible to perform cross-database queries with PostgreSQL?
- How do you get the index of the current iteration of a foreach loop?
- Datatable vs Dataset
- Converting bool to text in C++
- How do I REALLY reset the Visual Studio window layout?
- What good technology podcasts are out there?
- How do I remove an item from a stl vector with a certain value?
- How can I add reflection to a C++ application?
- Where can I find decent visio templates/diagrams for software architecture?
- How do you format an unsigned long long int using printf?
- Why is Git better than Subversion?
- What is Inversion of Control?
- How to read a value from the Windows registry
- What is a deadlock?
- Sprintf equivalent in Java
- Creating a custom JButton in Java
- CSS - Make divs align horizontally
- How does GPS in a mobile phone work exactly?
- How do I get the difference between two Dates in JavaScript?
- Best ways to teach a beginner to program?
- Generating (pseudo)random alpha-numeric strings
- Accessing post variables using Java Servlets
- How can you customize the numbers in an ordered list?
- Java and SQLite
- What do "branch", "tag" and "trunk" mean in Subversion repositories?
- Tab Escape Character?
- What is the easiest way to parse an INI File in C++?
- What does ** (double star/asterisk) and * (star/asterisk) do for parameters?
- fopen deprecated warning
- What static analysis tools are available for C#?
- How to tell which disk Windows Used to Boot
- How do I fix "for loop initial declaration used outside C99 mode" GCC error?
- When should you use 'friend' in C++?
- Length of a JavaScript object
- htmlentities() vs. htmlspecialchars()
- How to show a GUI message box from a bash script in linux?
- How do you set up use HttpOnly cookies in PHP
- C# loop - break vs. continue
- Get file version in PowerShell
- How do I download code using SVN/Tortoise from Google Code?
- How to loop through files matching wildcard in batch file
- Embed a PowerPoint presentation into HTML
- Reading Email using Pop3 in C#
- Select N random elements from a List<T> in C#
- What is tail recursion?
- grep a file, but show several surrounding lines?
- What's the difference between struct and class in .NET?
- Get OS-level system information
- How do I merge two dictionaries in a single expression (taking union of dictionaries)?
- What are the main performance differences between varchar and nvarchar SQL Server data types?
- LINQ query on a DataTable
- Execute script after specific delay using JavaScript
- Calling the base constructor in C#
- How can I pass arguments to a batch file?
- How to easily consume a web service from PHP
- Execute a large SQL script (with GO commands)
- Mercurial stuck "waiting for lock"
- Getting all types that implement an interface
- How do I tell Maven to use the latest version of a dependency?
- How to catch SQLServer timeout exceptions
- What are the proper permissions for an upload folder with PHP/Apache?
- What is the correct way to create a single-instance WPF application?
- What are MVP and MVC and what is the difference?
- Best Practices for securing a REST API / web service
- T-SQL stored procedure that accepts multiple Id values
- Best JavaScript compressor
- Sending email in .NET through Gmail
- Parse usable Street Address, City, State, Zip from a string
- What is reflection and why is it useful?
- How can I represent an 'Enum' in Python?
- What's the best way to validate an XML file against an XSD file?
- How do you get a directory listing in C?
- What is the single most influential book every programmer should read?
- Setting a div's height in HTML with CSS
- How do I style (css) radio buttons and labels?
- Why functional languages?
- How can I play sound in Java?
- What is the regex pattern for datetime (2008-09-01 12:35:45 )?
- Remove duplicates from a List<T> in C#
- Boolean Field in Oracle
- When do you use the "this" keyword?
- Are PHP Variables passed by value or by reference?
- How to generate a core dump in Linux on a segmentation fault?
- Passing $_POST values with cURL
- How to change the icon of .bat file programmatically?
- How can I develop for iPhone using a Windows development machine?
- Embedding Windows Media Player for all browsers
- Python, Unicode, and the Windows console
- How do you move a file?
- Internet Access in Ubuntu on VirtualBox
- What is the Difference Between Mercurial and Git?
- Easy way to write contents of a Java InputStream to an OutputStream
- Center text output from Graphics.DrawString()
- x86 Assembly on a Mac
- Best GUI designer for eclipse?
- What is the difference between the | and || or operators?
- Disable browser 'Save Password' functionality
- Recommended add-ons/plugins for Microsoft Visual Studio
- Using ConfigurationManager to load config from an arbitrary location
- How to generate a random alpha-numeric string
- How to decode viewstate
- mysqli or PDO - what are the pros and cons?
- SQL Query for Logins
- Equivalent VB keyword for 'break'
- SQL Client for Mac OS X that works with MS SQL Server
- What is a lambda (function)?
- How do I list the symbols in a .so file
- Performing a Stress Test on Web Application?
- Reading from text file until EOF repeats last line
- How to set encoding in .getJSON jQuery
- How do I get the current location of an iframe?
- How do I load an org.w3c.dom.Document from XML in a string?
- How do I find the authoritative name-server for a domain name?
- What Ruby IDE do you prefer?