aman_naughty's blog

Time Complexity Confusion!!!
By aman_naughty, history, 6 years ago, In English

Why does this code get accepted 55539853 and this does not 55539543?

I believe the time complexity of 1st submission is O(k(n+m)) for k bfs and then O(nklog(k)) for sorting each node.

Can someone tell the complexity of the second code because of which it is failing.

For getting s smallest element I am using slog(s) complexity in bfs in 2nd submission.

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

your accepted solutions runs in 1.7 second, which is close to the time limit, so sort vector is faster than popping from priority queue one by one, and therefore you get TLE?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Also, please learn to ask question instead of just posting codes. You can say like: solution 1 uses priority_queue and popping one by one while solution uses vector and sorting it. This will reduce the time taken for people to help you and therefore it will be more likely for someone to help.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      But ain't it the same thing. Sorting n elements O(nlog(n)) Popping priority queue O(log(n)) for 1 element so O(nlog(n)) for n elements??

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, it is the same in terms of time complexity. But having the same time complexity does not imply that the code is equally fast. For instance, sorting the code 1 time is O(nlog(n)), but sorting it twice is also O(nlog(n)), but is the performance of both code going to be the same?

        → Reply