zenwraight's blog

Need Help with understanding the Time complexity of the following code in c++?
By zenwraight, history, 6 months ago, In English

Hi Folks, I came across a piece of code and I am having a hard time figuring out the time complexity of the code. Here is the code:-

This is just for example purpose, basically the q has N values, just for example purpose, I am considering N=3. 

map<string, queue<int>> m;
queue<int> q;
q.push(0);
q.push(1);
q.push(2);
m["key"] = q;
queue<int> temp = m["key"];

I want to know will the time complexity of this piece of code be O(1) or O(N)?

My understanding says that it's O(N) because of line queue<int> temp = m["key"] , as we copy the queue to a new variable.

Any pointers or help is greatly appreciated.

Thanks Folks :)

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

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

O(1) because there is no any N at all

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

    [user:oversolver]Thanks a lot for your response Sir, so if the q had size N and m["key"] = q.

    Then would this line queue<int> temp = m["key"] take O(N) time? Basically I want to understand that if I try to store the queue value to an auxiliary queue temp, does it perform this operation in O(1) or O(size of the queue)?

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

      Probably yes, copying a $$$N$$$ sized queue (or even vectors, strings, sets, etc.) takes $$$O(size)$$$ time.

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

According to this, it should be O(1) (or O(log) because of the map?)

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

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

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

If the queue size is N and the map size is M then firstly look up through the map will take log(M) time + O(N) time to copying all the values to queue.

→ Reply