Some Non-intuitive Doubts

Revision en18, by meet2410shah, 2021-01-22 22:17:31

There are times when I want to predict the time complexity or space complexity of the algorithm and want to check whether it fits into the given constraints or not. It always looks like that the approach is correct but there are some architecture-level problems or rather concepts that I don't know very well.

Here are my doubts,

1. It is given that the problems need to solve in a time limit of 1 or 2 seconds and the memory limit of 256 Megabytes or 512 Megabytes. When do we need to consider those constraints while computing the complexities?

2. What should be the maximum size of the array that we can declare?

3. How to select the STL container that fits best to solve the problem? (Although it depends on the problem)

4. In case of double for loop. How do we need to access the matrix (generally in DP problems) to make sure that it will not exceed the time limit? How should I write for loops bigger one outside or the smaller one? Do we need to create a matrix of N x M or M x N (i.e., N = 100 & M = 10000), and the reason for it?

5. How writing array outside of the main helps us to reduce the time complexity?
Example CSES Problem: Coin Combinations II
TLE Code: https://cses.fi/paste/c63f02b96710bdd1164250/
ACCEPTED CODE: https://cses.fi/paste/4098290d90c8bb29164255/

6. How to use the Modulo operator effectively to reduce the time complexity?
Example CSES Problem: Coin Combinations I
TLE Code: https://cses.fi/paste/bd61629529d99d8b163f51/
Modulo is written inside both loops.
ACCEPTED CODE: https://cses.fi/paste/753f06b17cbe2b761640d5/
Modulo is written outside of the inner loop.

I need help to understand the exact mathematics and concept of computer architecture behind the calculation of time and space.

Thank You.

#### History

Revisions

Rev. Lang. By When Δ Comment
en23 meet2410shah 2021-04-12 09:43:42 0 (published)
en22 meet2410shah 2021-04-12 09:43:08 27 Numbering change
en21 meet2410shah 2021-04-12 09:42:18 0 Tiny Change
en20 meet2410shah 2021-04-12 09:41:34 8 Tiny change (saved to drafts)
en19 meet2410shah 2021-04-12 08:43:28 30 Link Edited
en18 meet2410shah 2021-01-22 22:17:31 0 (published)
en17 meet2410shah 2021-01-22 22:16:19 41
en16 meet2410shah 2021-01-22 22:15:36 4 Tiny change: ' space. Thank You.' -> ' space. \n\nThank You.'
en15 meet2410shah 2021-01-22 22:15:16 2 Tiny change: 'nd space. Thank You' -> 'nd space. Thank You'
en14 meet2410shah 2021-01-22 22:15:00 48
en13 meet2410shah 2021-01-22 22:13:40 23 Tiny change: 'M = 10000)?\n\n5. Ho' -> 'M = 10000), and the reason for it?\n\n5. Ho'
en12 meet2410shah 2021-01-22 22:12:08 63
en11 meet2410shah 2021-01-22 22:10:17 156
en10 meet2410shah 2021-01-22 22:06:48 30
en9 meet2410shah 2021-01-22 22:05:49 279
en8 meet2410shah 2021-01-22 22:01:14 2 Tiny change: 'oth loops.\n ACCEP' -> 'oth loops. \n ACCEP'
en7 meet2410shah 2021-01-22 22:01:00 4 Tiny change: 'oth loops. \n\n ACCEP' -> 'oth loops.\n ACCEP'
en6 meet2410shah 2021-01-22 22:00:33 4 Tiny change: '55/) \n\n5) How to us' -> '55/) \n\n6. How to us'
en5 meet2410shah 2021-01-22 22:00:09 18
en4 meet2410shah 2021-01-22 21:59:40 672
en3 meet2410shah 2021-01-22 21:52:03 16
en2 meet2410shah 2021-01-22 21:51:31 11
en1 meet2410shah 2021-01-22 21:50:50 985 Initial revision (saved to drafts)