Solution taking higher time on small contraints

general
1

I recently solved a question where my algo has complexity of O(N).

Surprisingly, on constraint where N<=1000, Solution takes 0.97 seconds ; but on constraint where N<=100000 ;
it takes 0.00 seconds (C++ Solution). Why is that happening…??? And even why at a constraint of N<=1000 ; solution is taking nearly 1 second time even in C++ ?

This is the link to My Solution for this problem

I have recently began to upsolve problems in C++ and am new to language… Please help…

1 Like
2

It actually took me a while to figure it out why the hell is this happening for smaller test cases .

But if you see it clearly then 0.97s is for 70 pts.

The subtasks are placed in wrong order in your submission page .

https://www.codechef.com/viewsolution/21917673

3

okayy I got it… Thanks a lot.

But one extra thing @raj_13 … Could you please help me understand that if my code had a complexity of O(N) ; and constraints N<=100000 ; why even the run time goes nearly to 1 second…???

I am trying to shift to C++ because it is way faster than python. But even that seems quite slow…

Please help

4

Whenever adding a character to a string use ‘+=’ operation i.e.

ans += “B”
instead of
ans=ans+“B”

First operation just adds character B to the string whereas the second operation makes a copy of first string, adds character and then assigns to the original string. Therefore your code might look like O(n) but its not.

5

thank you @alpha_q2

I didn’t knew the difference between ans += “B” and ans=ans+"B"

Finally Had a fast submission and learnt something new… THANKS :slight_smile:

1 Like