.dragonman164's blog

Can someone tell me Time complexity and Space Complexity of this Code? I am confused about it.
By .dragonman164, history, 15 months ago, In English

I want to find out time complexity and space complexity of this code.

https://cses.fi/paste/4c432ea7de710eac40593c/

I was trying to solve this task but I was getting TLE.

https://cses.fi/problemset/task/1734

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by .dragonman164 (previous revision, new revision, compare).

→ Reply
»
15 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Wow, you really have no clue. I guess you just think that segment tree is magic.

Time complexity is $$$O(n \log^2 n + qn \log n)$$$, space complexity is $$$O(n \log n + qn)$$$ ($$$qn$$$ part might not be true, I'm not sure how is it measured).

→ Reply