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){
stack.add(1);
}
else{
stack.add(2);
}
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);
```

Problem link: https://codeforces.com/contest/1810/problem/B

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

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

Auto comment: topic has been updated by pranp_24 (previous revision, new revision, compare).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

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?

The stack operations are running in O(n) time. This blog talks about it with the solution just being a linked list.

Please elaborate how is it O(n) operations

I really doubt something called

`Stack`

would ever have a .push and .pop running in O(n) time.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.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.I didn't realize System.out.print was so slow. This makes sense, thank you!