0

What is the time complexity to calculate 2^5000 ?

I approached it, by recursion but then it leads to O(N) where N = power of a number. Is there any way to reduce this time complexity ?

Garrick
  • 677
  • 4
  • 15
  • 34
  • 5
    2^5000 is a constant, not an algorithm. Time complexity relates algorithms with some set of parameters, typically just 'n', with n tending to infinity. It makes no sense to ask for n=5000. You also need to specify the algorithm: a lookup table? shifting 1 left n times? some other calculation? – Ian Mercer Oct 12 '16 at 05:22

1 Answers1

1

I think that you are interested in general approach, not only in this given example.

You can calculate N-th integer power using Log(N) operations with exponentiation by squaring approach

But note that number 2^N consists of about N binary digits (bits) and simple writing in memory is O(N) operation

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Thanks for the link. It covers all aspects . – Garrick Oct 12 '16 at 05:28
  • http://stackoverflow.com/questions/5231096/time-complexity-of-power. Is is saying thar time complexity is O(log b) – Garrick Oct 12 '16 at 05:40
  • "simple writing in memory is O(N) operation: - Can you elaborate this. – Garrick Oct 12 '16 at 05:43
  • 1
    Yes, I said the same. – MBo Oct 12 '16 at 05:43
  • But, i didn't understand the last line. plz elaborate – Garrick Oct 12 '16 at 05:45
  • 1
    Theoretic analysis might consider that numbers are suitable in machine words (2-4-8 bytes). Reading and writing such number is O(1) operation. But long numbers occupy many bytes (O(N) for N-th power). – MBo Oct 12 '16 at 05:46
  • It means that to store the result of this computation requires O(N), right ? – Garrick Oct 12 '16 at 05:48
  • 1
    Yes, it does. Moreover, the last long-number multiplication will take O(NlogN) time. Against - theoretic analysis might omit such ' dirty details'.... – MBo Oct 12 '16 at 05:49
  • Thanks, i got it now !! – Garrick Oct 12 '16 at 05:50
  • `note that number 2^N consists of about N binary digits (bits) and simple writing in memory is O(N) operation` - even worse: if you want that number in decimal, you may be better off to compute in a decimal-oriented number representation to begin with - and repeatedly multiplying (table lookup?) may be fastest. – greybeard Oct 12 '16 at 20:14