adamantium's blog

What is the actual complexity of 620C
By adamantium, history, 9 years ago, In English

In 620C - Pearls in a Row I watch some source code of other people. Most of them used map. They iterate for n times and count the element of the array using map when they find that the value of current element in the map is 2 then they clear the whole map.. For that I am bit confused about that solution. It will be pleasure if anyone tell me what is the actual complexity of that solution :)

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

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

to delete all the elemants in map take O(N) where N is size of map

sum of all the sizes of map during program, about what you have said, is N

so such solution as you say take O(N + NlogN)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Best way to do it is using set just because we dont need to count elements : we only need to know if this element was before. Anyway, in java you can clear map(in my case set) with O(1) complexity like this:

set = new TreeSet<>();

BTW, if we change it to HashSet(unordered_set in c++), we can get O(n) complexity.

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

    If I'm not mistaken, old set will be cleared away by GC, and it will still take O(n) time

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

      Old set will be cleared by GC of corse but please explain me why do you think that it take O(n) time?

      I don't know right answer, but I can share my thoughts: complexity is O(1) because we don't remove each element separately, we remove the whole object from the memory.

      Anyway, I made an experiment and get some data which confirms my thesis:

      k = 5
	Adding time: 0
	Clearing time: 0
k = 10000
	Adding time: 8
	Clearing time: 0
k = 1000000000
	Adding time: 7316
	Clearing time: 0
      → Reply