DSA : Day 2

Understanding Problem Constraints and Time Complexity

Happy Learning! Happy Programming!

Topics

1?? Relation of Constraints and Data Types

2?? Relation of Constraints and Time Complexity

3?? Time Complexity

Relation of Constraints and Data Types

??Range of Data Types

• ?2×10^9 < int < 2×10^9
• ?9×10^18 < long long < 9×10^18

??Case Study

Will the code work upon the following constraints?? If not, at which position should the data type be changed?

??1<N<10^5 and -10^4<=arr[i]<10^4

• Worst Case: arr[i] = 10^4 and N = 10^5
• Then, sum = N*arr[i] = 10^9
• All arr[i], N, sum are in the range of 'int'.

??1<N<10^4 and -10^6<=arr[i]<10^6

• Worst Case: arr[i] = 10^6 and N = 10^4
• Then, sum = 10^10
• arr[i], N are in the range of 'int'.
• sum is not in the range of 'int' ? change it to 'long'/'long long'
• Positions to change in fig. : 1, 4

??1<N<10^5 and -10^9<=arr[i]<10^9

• Worst Case: arr[i] = 10^9 and N = 10^5
• Then, sum = 10^14
• arr[i], N are in the range of 'int'.
• sum is not in the range of 'int' ? change it to 'long'/'long long'
• Positions to change in fig. : 1, 4

??1<N<10^5 and -10^11<=arr[i]<10^11

• Worst Case: arr[i] = 10^11 and N = 10^5
• Then, sum = 10^16
• N are in the range of 'int'.
• arr[i], sum is not in the range of 'int' ? change it to 'long'/'long long'
• Positions to change in fig. : 1, 2, 4

??1<N<10^10 and -10^6<=arr[i]<10^6

• Worst Case: arr[i] = 10^6 and N = 10^10
• Then, sum = 10^16
• arr[i] are in the range of 'int'.
• N, sum is not in the range of 'int' ? change it to 'long'/'long long'
• Note: the data type of iterator i will also change, as it depends on data type of N
• Positions to change in fig. : 1, 4, 2, 5

??1<N<10^10 and -10^11<=arr[i]<10^11

• Worst Case: arr[i] = 10^11 and N = 10^10
• Then, sum = 10^21
• arr[i], N is not in the range of 'int' ? change it to 'long'/'long long'
• sum is not in the range of 'long'/'long long' also
• Positions to change in fig. : 1, 2, 4, 3, 5

Relation of Constraints and Time Complexity

??Analysis

In general, let us consider the processor is of 1GHz and limit of runtime is 1 sec.

Then, # instructions that can be executed = 10^9

Considering, each iteration performs 10 instructions.

Therefore, # iterations in total = 10^8.

Hence, for any solution, the number of iterations should be less than 10^8.

For example, if each testcase requires 'M' time, then for 'T' testcases,

Total # iterations = T*M , which should be less than 10^8.

??Case Study

Let us consider the problem below for analyzing.

??Sol A: O(N) --> Applying loop and multiplying A for B times

• Constraints Case 1

1. N = B = 10^3 and T = 10^3
2. # iterations = T*N = 10^6
3. 10^6 < 10^8 (Works!)
4. Let us, check the datatype also, result of A^B = 10^(10^3 * 6) = 10^6000 (Very Large!! --> that's why problem mentions to take modulo)
5. Data type of A = int, B = int, result = long long

• Constraints Case 2

1. N = 10^9 and T = 10^3
2. # iterations = T*N = 10^12
3. 10^12 !< 10^8 (Code Doesn't Work! --> Reduce time complexity)

??Sol B: O(logN)

• Constraints Case 1

1. N = B = 10^3 and T = 10^3
2. # iterations = T*(log2(N)) = 10^3*(log2(10^3)) ~ 10^3*(log2(2^10)) ~ 10^4
3. 10^4 < 10^8 (Works!)

• Constraints Case 2

1. N = 10^9 and T = 10^3
2. # iterations = T*(log2(N)) = 10^3*(log2(10^9) ~ 10^3*(log2(2^20)) ~ 2*10^4
3. 2*10^4 < 10^8 (Works!)

Time Complexity

O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)