Simple mistake that some people make when analysing time complexity

Revision en9, by Peter-007, 2023-04-18 18:41:31

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian Peter-007 2023-04-19 14:55:24 11
ru2 Russian Peter-007 2023-04-19 09:57:02 20
en12 English Peter-007 2023-04-19 09:56:03 20 Tiny change: 'to [user:xcsjerry,202' -> 'to [user:xksjerry,202'
ru1 Russian Peter-007 2023-04-18 20:45:23 1084 Первая редакция перевода на Русский
en11 English Peter-007 2023-04-18 20:32:04 38 Tiny change: 'to divide time complexity by $k!$. ' -> 'to divide running time by $k!$. '
en10 English Peter-007 2023-04-18 18:43:17 121
en9 English 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 English Peter-007 2023-04-18 18:40:34 0 (published)
en7 English Peter-007 2023-04-18 18:39:46 207 Tiny change: '023761).\nBut for ' -> '023761).\n\nBut for ' (saved to drafts)
en6 English Peter-007 2023-04-18 00:38:07 0 (published)
en5 English Peter-007 2023-04-18 00:35:04 5
en4 English 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 English Peter-007 2023-04-18 00:33:30 12
en2 English Peter-007 2023-04-18 00:32:24 716 Tiny change: 'em for you\nYou are ' -> 'em for you.\n\nYou are '
en1 English Peter-007 2023-04-17 23:19:44 304 Initial revision (saved to drafts)