How should we decide the complexity of the code based on input description given?

Revision en6, by kuldeep_devulapally, 2024-04-17 22:17:01

I have given two input description given for two different problems in codeforces.

Description-1:-

Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (2≤n≤10^5) — the length of the array a.

The second line of each test case contains n integers a1,a2,…,an(0≤ai<n) — the elements of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Description-2:-

The first line contains a single integer t (1≤t≤5⋅104) — the number of test cases.

The only line of each test case contains a single integer n (1≤n≤10^5).

Here my doubt is can we perform O(n) on both the questions or not and performing O(n) operations on 2nd one is getting me TLE. So how should i approach questions based on their complexity?

How important is this line in 1st input description:- It is guaranteed that the sum of n over all test cases does not exceed 10^5.

PS:- Thank You! my doubt has been clarified and what we can understand from this line is the sum of n over all testcases doesn't exceed 10^5 and we can perform O(N) operations on this problem within given time limit so the total numbers inputting will be T+N i.e 10^4+10^5 not T*N i.e 10^4*10^5 which can be done within 1 sec...

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English kuldeep_devulapally 2024-04-17 22:17:01 6 Tiny change: 'ations on 1st one is ge' -> 'ations on 2nd one is ge'
en5 English kuldeep_devulapally 2024-04-17 21:09:55 332
en4 English kuldeep_devulapally 2024-04-17 17:21:54 134
en3 English kuldeep_devulapally 2024-04-17 17:20:36 130
en2 English kuldeep_devulapally 2024-04-17 17:17:57 38
en1 English kuldeep_devulapally 2024-04-17 17:14:55 1309 Initial revision (published)