So i don't really understand how I will calculate the time complexity for my code, I've had a hard time with it and I would really need some help.

the exponent is N all the time. So how will i find the time complexity in N-time(bits)..

for(int i = 0; i < powerup(2, exponent); i++)
      candenc = KEYsubsetsum(candidate, T);
      m.insert(pair<Key, Key>(candenc, candidate));

   ckey = candidate;


      candenc = KEYsubsetsum(candidate, T);
     if(mkey.find(encrypted-candenc) -> first + candenc == encrypted)

       auto range = mkey.equal_range(encrypted-candenc);
        for(multimap<Key,Key>::iterator it=range.first; it!=range.second; ++it)
cout << candidate + it->second << endl;

      candidate = candidate + contkey;

      } while (candidate != zero);

  auto end = chrono::high_resolution_clock::now();
  cout << "Decryption took "
       << std::chrono::duration_cast<chrono::seconds>(end - begin).count()
       << " seconds." << endl;

  return 0;
4 Years
Discussion Span
Last Post by vinayemani

Well, without knowing more about what your KEYsubsetsum() does, it's hard to reason about the time complexity of your code. Also, what exactly do ckey and contkey variables stand for? It seems like you are looping through every subset of N elements (0 to 2^N-1) and computing that subset's sum and storing it in a map. I'd guess the code has a lower bound of 2^n * n(big omega of 2^n * n) and we need more info for calculating the upper bound.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.