3

For the sake of the argument, consider following (very bad) sorting algorithm in python:

def so(ar):
    while True:
        le = len(ar)
        switch = False
        for y in range(le):
            if y+1 == le:
                break
            if ar[y] > ar[y+1]:
                ar[y],ar[y+1] = ar[y+1],ar[y]
                switch = True
        if switch == False:
            break
    return ar

I'm trying to understand the concept of "complexity of the algorithm" and there is one thing I don't get.

I came across the post that explains how to find the complexity of the algorithm here:

You add up how many machine instructions it will execute as a function of the size of its input, and then simplify the expression to the largest (when N is very large) term and can include any simplifying constant factor.

But well, the problem is, that I cannot calculate how many machine instructions will be executed just by knowing the length of the list.

Consider first example:

li = [random.randint(1,5000) for x in range(3000)]
start = time.time()
so(li)
end = time.time() - start
print(end)

Output: 2.96921706199646

Now have a look at the second example:

ok = [5000,43000,232] + [x for x in range(2997)]
start = time.time()
so(ok)
end = time.time() - start
print(end)

Output: 0.010689020156860352

We can see that the same sorting algorithm, two different lists, lists are the same length, and two completely different execution times.

When people are talking about algorithm complexity (big O notation) they normally assume that the only variable that determines complexity of the algo is the size of the input, but clearly, in the example above it is not the case. It is not only the size of the list, but also the positioning of each value within the list that determines the speed of the sorting.

So my question is, why do we only consider size of input when estimating complexity? And, if it is possible, can you tell me what the complexity of the algorithm above will be?

iwbtrs
  • 358
  • 4
  • 13
  • 4
    What you're referring to is the Big-O notation. In computational complexity theory, it is the worst-case run time. In your second example, you have an input that does not fit the definition of the worst case for this algorithm (in this case, because a major portion of it is already sorted). This is why there are other measures like best case, average case, etc. You might also be interested in reading this: https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array – inspectorG4dget Jul 21 '19 at 20:32
  • I'd recommend a textbook. A good hint towards understanding the answer to your question comes from realizing that in this context, one algorithm taking three times as long as another is completely irrelevant. At the speed and power of a computer, what we care about is how fast the complexity grows when we really try to overwhelm it with data. The only thing we can grow is the input. – Kenny Ostrom Jul 21 '19 at 20:39
  • 3
    Please don't accept an answer too fast. There might be better answers coming later, but other users might not bother to write anything if they see that an answer was already accepted. – Eric Duminil Jul 21 '19 at 20:46
  • If you look at the function you described, `so`, as a black-box - then the only thing changing is the size of the input - the list! Imagine it as a hardware component that came out of the factory, everything is already hard-wired. Only thing changing is what you feed it as input. So this is why we usually look at the size of the input. You want to see how drastically the time will change when changing the input – Tomerikoo Jul 21 '19 at 21:11
  • The sorting algorithm you posted is https://en.wikipedia.org/wiki/Bubble_sort The usual measure is number of comparisons, not number of machine instructions, but they probably differ by a constant factor ... making them identical. – Kenny Ostrom Jul 21 '19 at 23:27
  • @KennyOstrom - the number of swaps or moves should be considered as well as number of comparisons. – rcgldr Jul 22 '19 at 02:03
  • As answered by Roland Smith, it's by definition of big O time complexity. Going beyond this usually involves some form of analysis. For example when comparing quick sort and merge sort, merge sort does more moves, but fewer compares. If sorting an array of integers, quick sort is usually faster than merge sort (about 15% on current X86 processors), but in cases such as sorting an array of pointers to strings, the overhead of comparing strings is greater than the overhead of moving pointers, so merge sort ends up being faster. – rcgldr Jul 22 '19 at 02:07

3 Answers3

3

You're correct, complexity doesn't only depend on N. That's why you'll often see indications about average, worst and best cases.

Timsort is used in Python because it's (O n log n) on average, still fast for worst-cases (O(n log n)) and extremely fast for best-cases (O(n), when the list is already sorted).

Quicksort also has an average complexity of O(n log n), but its worst case is O(n²), when the list is already sorted. This use case happens very often, so it might be worth it to actually shuffle the list before sorting it!

Eric Duminil
  • 52,989
  • 9
  • 71
  • 124
2

why do we only consider size of input when estimating complexity?

In the narrow sense of complexity as of the use of Big O notation in computer science, it is simply by definition:

In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

In the broader sense your question could be interpreted as "why do we use Big O notation to describe algorithm complexity when the nature of the data can be just as important as its size."

The answer here lies in the fact that algorithm development is often done on small datasets to make it easy, while in the real world the datasets are huge. When you are writing your sorting function you're most likely going to try it first on small lists of random data. You'd want the result small enough that you can verify that it worked by simply looking at the result...

Roland Smith
  • 42,427
  • 3
  • 64
  • 94
0

The time complexity is not always definitely dependent on size of input. When we look at randomized sorting algorithms, the input patterns might play a significant role in determining time complexity.

We usually calculate time complexity in terms of worst, good and average case and could particularly study time complexity in terms of specific input order/patterns which could lead to good, average and best case time complexity.

For example, in first case provided by you, since input is randomized, there is 1/n! probability for a particular input to occur. The good case (when the list is sorted already) is Ω(n) and the worst case(when the list is reversely sorted) is O(n²) , but the probability is low for best or worst case to occur.

Therefore, the sorting algorithm has θ(n²) average time complexity since the probability of comparison and swap in case of two elements in average case input is high due to random distribution of numbers.

In the second case, the order is strict which means high probability for input to tend toward best case or worst case time complexity . In your case, input is more tending towards good case, therefore lesser time.

Achint Sharma
  • 355
  • 4
  • 11