What is the Time complexity of this Program?

help
,
1

I think it should be O(n*logn), but it seems it’s more then that…

//bo is a string consisting of '0's and '1's
for(int i=0;i<n;i++){
    int from=i,to=i;
    while(bo[i]=='1'){
        to++;
        i++;//<<<
    }
    sort(v.begin()+from,v.begin()+to+1);//<<<
}
2

worst time complexity is (n^2 * log(n)) when string is 000000000.

1 Like
3

Yes, that feels right. I was confused because I used this “here” on codeforces where n is 2e5 and somehow It got accepted. Why?

4

Because of amortized case ; P

5

Can you explain ? …

6

Amortized case means not all the test cases are big enough, some test cases are small and some are meet the constraints,
So if we calculate the overall computations of your code will be less than the worst case …

Because not every case is the case ; P

1 Like
7

So basically Test cases are weak ?

How will I know if my method will give AC in these kind of problems…

8

Yeah you can say that test cases are weak ; P