Why do we always consider worst case time complexity?

Question

Why are we only concerned about worst case time complexity (Big O), given a data set and 2 code snippets/algorithms, can we always be sure that the algorithms will take the worst case complexity?

score 1 · Answer 1 · answered Sep 09 '15 at 09:43

1

Short answer: you shouldn't just be concerned about worst case complexity.

If you have a practical bounded case, the constant factors can be much more important than the asymptotic complexity. Example: say you have a collection of 10 items. You can make O(1) lookup of these in a dictionary/map/hash table, or O(log N) lookup in a sorted list or O(N) lookup in an unsorted list.

For 10 items, the asymptotic complexity rarely matters. In fact, it's likely that the O(1) dictionary lookup will be slower than the O(log N) sorted list lookup because of bigger constant factors.

So you should only be concerned with asymptotic complexity when it matters, which is when you have "a lot" of something.

answered Sep 09 '15 at 09:43

Anders Forsgren

10,827
4
40
77

Then for algorithms why we take into consideration only Big O? We always decide which algorithm to use based on Big O. – Sreekanth Karumanaghat Sep 09 '15 at 09:54
1

I'm not sure why anyone would do that. Who is "we"? – Anders Forsgren Sep 09 '15 at 10:11
No I see always people discussing Big O when they have to choose between 2 algorithms. – Sreekanth Karumanaghat Sep 09 '15 at 10:14
2

That's because they are either 1) theoretically interested in the algorithm runtime and/or 2) know they have "many" items and small constant factors so O(N) runtime is important. But you must always *consider* the constant factors and the number of items, i.e. the real-world runtime! – Anders Forsgren Sep 09 '15 at 10:18

score 1 · Answer 2 · edited May 23 '17 at 12:29

1

We are not only concerned about worst case time complexity (or if you are, you shouldn't) - see also Meaning of average complexity when using Big-O notation. Average time is probably equally valid, but in many cases you want to make sure that an algorithm doesn't take a very long time. As an example of why you would care more about 'worst case': suppose you probably don't really mind if an algorithm takes 1 or 2 seconds*, but you want to make sure that at least it's not going to take an hour in some cases.

*Yes, obviously this is very important in many situations, but suppose it's a script you need to run one time.

And to the second part of your question: no, we cannot always be sure the 'more complex' algorithm will take the longest (I'm assuming that by 'taking the complexity', as you put it, you mean 'how long it actually takes in a particular situation'). A trivial counterexample is some kind of inefficient 'find (first instance of ...)' algorithm that just happens to get the specified item very quickly, as opposed to another good algorithm that just takes longer because it iterates over the file/array in a different order or direction. This will obviously depend on the data a lot, e.g. let's say the value you are interested in is more likely to occur around the end of the file/array.

edited May 23 '17 at 12:29

Community

1
1

answered Sep 09 '15 at 09:52

BrechtDeMan

6,589
4
24
25

My doubt is that for a programmer to decide whether to use a nested loop,with outer iterations m and inner iterations n, or whether to use a single loop of k iterations(assume both solves the problem) what all should he consider? Is it just Big O or are there other things? If Big O, then why? (Assume I want a solution that takes least time.) – Sreekanth Karumanaghat Sep 09 '15 at 09:58
1

My general response to all this is that it would really depend on the situation, the task, and your priorities (which could include aiming for fastest average case or fastest worst case). The question whether to use a nested loop or single loop doesn't really have a single answer (unless parallelisation is involved) and I can't really think of a general truth there, or a good code example. Also: yes, there are other things than Big O! See [Difference between lower bound and tight bound?](http://stackoverflow.com/questions/464078/difference-between-lower-bound-and-tight-bound) – BrechtDeMan Sep 09 '15 at 10:04
So how would a programmer in general choose an algorithm for a situation, suppose he knows the approximate size of the data set, say it is in millions, in that case is it possible to judge which will be efficient? – Sreekanth Karumanaghat Sep 09 '15 at 10:08
1

Then I think Big O is indeed a powerful tool, but it may not always be practical. I myself would go down a more empirical route and maybe test two 'versions' (provided they are easy enough to implement) on a data subset and measure how long it takes. – BrechtDeMan Sep 09 '15 at 10:11
Why is it all so complicated. Sigh! :( – Sreekanth Karumanaghat Sep 09 '15 at 10:13
1

Don't know if I can answer that :) I guess if these things were easy, we'd solve them/automate them, and move on to more complex things again. I think in most practical cases what you're asking is not super critical, and you can either test things empirically and thoroughly, or if you're in a hurry it's usually not a problem that your algorithm takes a few more seconds. – BrechtDeMan Sep 09 '15 at 10:19

score 0 · Answer 3 · edited Sep 15 '18 at 18:04

I think all three types of complexity matter. It depends on you that, what you want.

For Example, there is a tube of size x and you started filling it with water. To know when water will start overflowing you will find upper bound limit(size or capacity) i.e worst case how much liter water this tube can hold.

If you want to know about how your algorithm will behave in worst case i.e how much time and space will my algorithm take in the worst case then you need to go for BIG(o) i.e upper boundary.

Similarly, you can go for best and average too.

Why do we always consider worst case time complexity?

3 Answers3