1

I have return a below code in java to produce the possible binary representation of n digits.

public List<String> binaryRepresenation(int n){ List<String> list = new ArrayList<>(); if(n>0){ permuation(n, list, ""); } return list; } private void permuation(int n, List<String> list, String str){ if(n==0){ list.add(str); }else{ permuation(n-1, list, str+"0"); permuation(n-1, list, str+"1"); } }

For n=3, it produces 001 001 010 011 100 101 110 111 combinations. Overall this function produces 2^n possible representations.

Is it safe to say the time complexity is n * 2^n

Where 2^n time the method is called for base cases. In order to reach the each base case, it would have called the permutation method for maximum of n times.

So overall upper bound time complexity is n*2^n? Kindly correct me if i am wrong. I came to this conclusion based on the string permutation time complexity discussed in this thread Time Complexity of Permutations of a String . Your help will be much appreciated.

Improve this question
1
  • Time Complexity : 2^n Commented Jan 6, 2019 at 4:01

2 Answers 2

Reset to default
2

There is a small problem with your analysis. As you noticed, for each base case you have to call the function n times. But, some of those calls are being shared by other base cases. In other words, you are counting the same call multiple times.

This means that while the complexity definitely can't be greater than n * 2 ^ n, it might actually be lower.

To calculate a better bound on the complexity, you can count the actual number of calls to the permutation function. One way to do that is to consider the possible values of the str variable.

str will be a binary string of length less than or equal to n. Also, each call to the permutation function receives a unique value of str. This implies that the number of times the function is called is equal to the number of binary strings of length <= n.

How many such strings are there? 1 + 2 + 4 + ... + 2 ^ n = 2 ^ (n + 1) - 1

So, the number of times permutation is called is O(2^n). But each call includes the operations str + "0" and str + "1". These operations take O(n) time. So, the net time complexity of the operation is: O(n * 2^n) but for somewhat different reasons than you originally thought.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

It would be O(2^n), except that str+"0" and str+"1" each take O(n) time. So the complexity really is O(n*2^n), but not for the reason the OP imagines.
1

The time complexity is O(2n). Each function call pushes two new function calls onto the stack until the base case is reached. Visualize the tree for n = 3 as follows:

 ________""________ / \ ___0___ ___1___ / \ / \ _00_ _01_ _10_ _11_ / \ / \ / \ / \ 000 001 010 011 100 101 110 111

This is a perfect binary tree with 15 nodes and 8 leaves. 2n+1 states are visited, but we can remove the constant and simplify to O(2n).

String concatenation adds an n multiplier to the complexity, but using a StringBuilder or container with constant-time push/pop or add/remove operations should eliminate this, suggesting that that is only an implementation detail specific to your posted code, and not the algorithm's complexity in general.

Improve this answer

2 Comments

Possibly, but what is your rationale? Your newly-added answer is tautological. The only explanation is "In fact, the time complexity stays ϴ(p^n) even if you perform any polynomial amount of work in addition to the recursive call" -- but why is this the case? It's counterintuitive that using an O(1) string concatenation would yield the same overall time complexity as a linear concatenation incurred an exponential number of times so there would need to be a compelling rationale for disregarding it.
Thanks for taking the time to add to your answer. I don't have the mathematical background to understand your proof, but it still seems like you're making a leap by saying effectively "there's a general form and we can simply drop the polynomial work just because we can" before even starting the proof. I want to believe because you clearly have more background in this than I do, but I'm not seeing it.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.