Timeline for How does knowing the input size make the time complexity of a function constant?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 9, 2022 at 23:30 | comment | added | Nathan | @northerner Suppose you have N people playing bingo, and a list of 100 bingo numbers to call. For each person, you traverse through up to 100 bingo numbers to see how many numbers it takes for that person's bingo card to win. The upper bound on the time required do this grows based on how many people are playing (N). It does not grow based on the bingo numbers because they're a fixed/known amount of work (up to 100 comparisons, but never more than that.) Time to compute grows arbitrarily high as the number of people grows arbitrarily high, but the number of bingo numbers stays constant at 100. | |
| Apr 23, 2021 at 7:31 | vote | accept | northerner | ||
| Mar 14, 2021 at 9:22 | comment | added | Jörg W Mittag | Just look at the definition of Big-O: f ∈ O(g) if there exist constants c, N_0 > 0, such that for all n > N_0, f(n) <= c × g(n). Just set N_0 = 101. | |
| Mar 14, 2021 at 9:12 | comment | added | northerner | Still don't get it. With that reasoning wouldn't everything have time complexity of O(1) because there will always be a constant number of operations? For example binary search is O(logn) but using your argument, on a certain input it will always take the same operations therefore O(1). | |
| Mar 13, 2021 at 21:48 | history | edited | Jörg W Mittag | CC BY-SA 4.0 |
added 1813 characters in body
|
| Mar 13, 2021 at 21:34 | history | answered | Jörg W Mittag | CC BY-SA 4.0 |