main function is calling generateSubset with a string as argument. please confirm the following doubt.
complexity of generateSubset = O((2^n)-1)
complexity of filterChar = O(i)
total complexity = O(((2^n)-1)* log i )
please confirm this
Complexity of code
Time complexity is always expressed in terms of the size of the input. i here is a local variable.
the complexity here can be given as O(2^n * logn). each filterChar takes logn time and it runs 2^n times in total.
But in the lecture @Prateek-Narang-10209158320224419 Sir mentioned that complexity of filterchar is O(n)
can you share the link of the lecture plz
here the function filterChars works in log of the input provided to it (2nd parameter). But the input provided to it is of the order 2^n so it reduces to log(2^n) which is equal to n. So the complexity of the code is O(2^n *n) only, as said in the video. Sorry for the earlier confusion.