Daily Algorithm Practice: Big O, VI.11

 Yeah, I'm redoing this one because last time got messy. 

So. I got STUCK on this one. I kept staring at it and the solution, trying to understand it, and I just couldn't figure out why it was O(kc^k). So, I took a look at this StackOverflow explanation.

I was still confused but finally got it after a lot of rereading and deliberation. Or at least, I think I get it, and I will do my best to explain it here. 

Every time you generate a character to add to the end of a string, which you do inside of that for loop inside of printSortedStrings(), you have c possible characters that could be the next letter. c being the number of characters in the given alphabet. Since the strings are of length k, this happens k times. c is multiplied by itself k times. Thus, c^k. This can be verified by writing out very small strings and counting out each possible option -- the math checks out. 

c^k, then, represents how many strings we are working with, at a minimum, to check if they are sorted. We check whether or not they're sorted just before unwinding from each branch of recursion, when the whole string has been built, so for each of the c^k number of strings. Checking if they're sorted relies on the isInOrder() function, which is called for every single string and is O(k) on its own. 

As a result, the complexity of this entire thing is O(kc^k). 

That one was tricky. Took me a couple of days of deliberation and getting stuck, and I'll probably have to revisit it again later. The first solution was helpful but it also assumed that we were using Java, which meant it got super technical about the second part of the analysis -- While this looks like Java code, that was never explicitly stated, so I figure we can just go with the high-level analysis. The valuable part is the c^k part which was quite confusing for me at first.