Simple mistake that some people make when analysing time complexity

Правка en10, от Peter-007, 2023-04-18 18:43:17

Here's a simple problem for you.

You are given $$$n=200$$$ elements and you have to iterate over all possible quadriplets (4) of them, the order of elements of each quadriplet doesn't matter, and you can take same element more than one time. Give quick approximation of how many iterations will algorithm run.

Answer

It is not $$$1,6*10^9$$$

So if you have to iterate over all subsets of length $$$k$$$, it is important to remember to divide time complexity by $$$k!$$$. In fact, if $$$k=6$$$, you can fit in one second with $$$n<=85$$$, while $$$85^6≈3*10^{11}$$$, but you would iterate only $$$≈5*10^8$$$ subsets, and not knowing that you might not even think of it.

I hope this blog will help, because I was doing same mistake for a long time.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru3 Русский Peter-007 2023-04-19 14:55:24 11
ru2 Русский Peter-007 2023-04-19 09:57:02 20
en12 Английский Peter-007 2023-04-19 09:56:03 20 Tiny change: 'to [user:xcsjerry,202' -> 'to [user:xksjerry,202'
ru1 Русский Peter-007 2023-04-18 20:45:23 1084 Первая редакция перевода на Русский
en11 Английский Peter-007 2023-04-18 20:32:04 38 Tiny change: 'to divide time complexity by $k!$. ' -> 'to divide running time by $k!$. '
en10 Английский Peter-007 2023-04-18 18:43:17 121
en9 Английский Peter-007 2023-04-18 18:41:31 17 Tiny change: '{n^k}{k!}$ since you can h' -> '{n^k}{k!}$, logic behind that you can h'
en8 Английский Peter-007 2023-04-18 18:40:34 0 (published)
en7 Английский Peter-007 2023-04-18 18:39:46 207 Tiny change: '023761).\nBut for ' -> '023761).\n\nBut for ' (saved to drafts)
en6 Английский Peter-007 2023-04-18 00:38:07 0 (published)
en5 Английский Peter-007 2023-04-18 00:35:04 5
en4 Английский Peter-007 2023-04-18 00:33:54 13 Tiny change: '≈6*10^7$\n[cut]\n</spoiler>\n\nIt is no' -> '≈6*10^7$\n</spoiler>\n[cut]\nIt is no'
en3 Английский Peter-007 2023-04-18 00:33:30 12
en2 Английский Peter-007 2023-04-18 00:32:24 716 Tiny change: 'em for you\nYou are ' -> 'em for you.\n\nYou are '
en1 Английский Peter-007 2023-04-17 23:19:44 304 Initial revision (saved to drafts)