Timeline for Time complexity of min() and max() on a list of constant size?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 30, 2021 at 11:27 | comment | added | northerner |
Obviously writing a loop to iterate over each element of the list would have run time O(n) (infact Θ(n)) where n is the number of items in the list. i.e. for(int i = 0; i < list.length; i++) if(list[i] > max)...
|
|
| Dec 30, 2021 at 11:22 | comment | added | northerner | @JoshRumbut when we talk about "fixed size" input or "input growing towards infinity" what exactly do we mean? Fixed size at compile time or runt time? For example most algorithms like quicksort does not take more input after it has started so in that sense the input is fixed size. | |
| Dec 30, 2021 at 9:20 | comment | added | Josh Rumbut | @northerner remember that the idea of big O notation is to describe a function's behavior as the input grows toward infinity. If the input isn't allowed to grow toward infinity, then big O is not that useful. You could just calculate the exact number of operations needed to sort a 100 item list. Does that help? | |
| Dec 30, 2021 at 9:12 | comment | added | Josh Rumbut | @northerner the time complexity of Quicksort depends on the size of the input (n). In this question the size of the input is constrained, so the time complexity doesn't vary in the unusual way. I suppose for sorting you could do a different sort of analysis, describing the worst case run time based on other properties of the fixed sized list (if it's pre-sorted randomly, already in order, in reverse order, etc). | |
| Dec 29, 2021 at 8:03 | comment | added | northerner | Then how come we say other algorithms are O(nlogn)? For example with quicksort the input certainly is a fixed size but that doesn't give it time complexity of O(1). Why doesn't the same reason apply to it? | |
| Mar 12, 2021 at 13:55 | history | edited | Josh Rumbut | CC BY-SA 4.0 |
Made more explicit assumption about types
|
| Mar 12, 2021 at 9:58 | comment | added | Martin Rosenau | Depends what "constant sized list" means: It may mean: A list with a given number of elements but the elements may have different sizes. Example: A list of strings which can have one character or 10.000 characters. The "size of the input" of the list of 100 elements, each of one character length, differs from the list of 100 elements, each of 10.000 characters length. | |
| Mar 12, 2021 at 4:20 | review | First posts | |||
| Mar 26, 2021 at 4:21 | |||||
| Mar 12, 2021 at 4:19 | history | answered | Josh Rumbut | CC BY-SA 4.0 |