pranp_24's blog

Can't understand time complexity
By pranp_24, history, 18 months ago, In English

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.net/contest/1810/problem/B

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

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
18 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
18 months ago, # |
  Vote: I like it -25 Vote: I do not like it

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

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please elaborate how is it O(n) operations

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I really doubt something called Stack would ever have a .push and .pop running in O(n) time.

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

→ Reply