Time complexity

#1

How are we supposed to know what time complexity linear quadratic since it isn’t specified in the question.

#2

#include<bits/stdc++.h> using namespace std; int main() { int test; cin >> test; while(test>0) { int n; cin >> n; int a[n]; int sum[n]; for(int i=0;i<n;i++) { cin >> a[i]; sum[i]=sum[i-1]+ a[i]; } int max=a[0]; for(int i=0;i<n;i++) { for(int j=i;j<n;j++) { int currsum=0; currsum=sum[j]-sum[i-1]; if(currsum > max) { max=currsum; } } } cout << max << endl; test–; } }

#3

hello @gaganpreetsachdev1
did nt get ur question.
do u mean what is the time complexity of this program?

we have two nested loops due to which its time complexity will be O(n^2). (I,E QUADRATIC)

#4

there is O(n^2) and O(n^3) as well. How are we supposed to know which one we got to use since it wasn’t specified in the question

#5

I used O(n^2) only but it didn’t satisfy the test cases please have look in my code

#6

u will never be given any time complexity in any question.

u need to figure it out on ur own . by looking at the constraints.

#7

for this problem u need o(n) algorithm to pass all the test case.

so use kadane .

#8
#9

this is again O(n^2).

it will not pass.

#10

How do you figure out through constraints?? Please explain

#11

pls refer this->https://www.geeksforgeeks.org/knowing-the-complexity-in-competitive-programming/

#12
#13

Still not coming please check

#14

a) use long long in place of int . because sum might excced the range of int.

b) intialisew ur max with a[0] ( doing this will handle the case when some or all elements are negative)

c) interchange position of these two if statement (again , we r doing this to handle negative case)
image
interchange the positions of these two if statements

#15
#16

You meant this right?

#17

yeah ,declare ur max as long long

#18
#19

Bro still it isn’t satisfying all the test cases

#20

image
u have to print max na?
why r u printing sum