### pranp_24's blog

By pranp_24, history, 4 months ago,

I was just working on a problem and I can't understand why one of my solutions passed and the other didn't.

I have two loops that are the same complexity. Since they are the same complexity, it should simplify to O(N)+O(N)=O(2N) which just becomes O(N). When I take out one of the loops, my solution passes, but when I keep them both in I get TLE. I don't understand this since they should simplify to the same complexity. Can someone please help?

Not accepted solution:

while(number>0){
if(number % 2==0){
}
else{
}
number/=2;
}

int originalsize= stack.size();
for (int i = 0; i < originalsize; i++) {
System.out.print(stack.pop()+ " ");
}


Accepted solution:

String ans="";
while(number>0){
if(number % 2==0){
ans="1 "+ans;
}
else{
ans="2 "+ans;
}
number/=2;
}
System.out.println(ans);


Accepted Solution: https://codeforces.com/contest/1810/submission/207920289

Not accepted Solution: https://codeforces.com/contest/1810/submission/207919439

• +5

 » 4 months ago, # |   0 Auto comment: topic has been updated by pranp_24 (previous revision, new revision, compare).
 » 4 months ago, # |   +11 Time complexity isnt really precise, so one O(n) can be slower than the other. For example you can imagine that if you do 100 for loops of 2 iterations it would be slower than if you do 1 for loop with 2 iterations, because 100>1. Big o notations are only invented as a relative measure.You can read more here
•  » » 4 months ago, # ^ |   0 I get that, but how am I supposed to know when O(2N) won't pass but O(N) will? This is a factor of 2, not 100, so shouldn't it be trivial?
 » 4 months ago, # |   -25 The stack operations are running in O(n) time. This blog talks about it with the solution just being a linked list.
•  » » 4 months ago, # ^ |   0 Please elaborate how is it O(n) operations
•  » » 4 months ago, # ^ |   0 I really doubt something called Stack would ever have a .push and .pop running in O(n) time.
 » 4 months ago, # | ← Rev. 2 →   +6 The reason you get TLE is because calling System.out.print is dreadfully slow. You should use PrintWriter instead, see 207955776. The reason you got TLE on one submission and AC on the other is simply because the TLE submission calls System.out.print more times than your AC submission. ... Since they are the same complexity, ... This is incorrect. Funnily enough, your TLE submission has strictly better time complexity than your AC submission. The reason is that operations like ans="1 "+ans; does not run in constant time. Prepending a character to ans runs in O(len(ans)) time.Btw, consider avoiding using Stack in Java. It is an old relic from the past. Use ArrayList or ArrayDeque instead, for example see 207955498.
•  » » 4 months ago, # ^ |   0 I didn't realize System.out.print was so slow. This makes sense, thank you!