Daily algorithm practice: Big O -- Cracking the Coding Interview, V1.10, started V1.11
Let's start:
While n is greater than 0. And n is getting divided by 10 every time. So we can say it's at least O(n), if not more efficient than that. Because we just keep dividing n by 10 until we get to 0. It really doesn't matter what's happening with sum, because that doesn't touch our while loop.
My initial instinct was to say O(n/10) which would just round to O(n) when you drop the constants, but this is not correct. I checked the answer key and found a different runtime.
The answer key says that "the runtime will be the number of digits in the number" but does not provide reasoning for this. So, we've got to go through it ourselves, and only then should we look into the actual mathematics behind the runtime.
The answer is in the problem description: "The following code sums the digits in a number." My confusion was that I didn't think it looped for every single digit, due to the dividing of n by 10. However, when it divides by 10 every time, this is actually directly correlated to how many digits the number has (which is why I'm glad I reviewed early math on Khan Academy). It's important here to realize that n is an INTEGER, NOT a double or float! So when we divide 50 / 10, for example, we have 5. Then we divide 5 / 10 and get 0.5 which rounds up to 1. Everything after that will round down to 0.
Also think about like 300. 300 / 10 is 30. 30 / 10 is 3. And 3 / 10 is 0.3. This still will run 3 times because it's a while loop, not a do-while, even though 0.3 rounds down to 0. So it will always run for the amount of times that we have digits.
I'm sure there's a far superior mathematical explanation for this, but I'm unaware as to what that is, currently. This one is also somewhat disorganized but I'll polish it once I actually post these to GitHub. I haven't decided yet if I'll do that after every chapter or not until the very end.
Well, now that we know this, we don't have a variable to represent this value, so we can't just blindly use it. We need to express it in terms of n. So, how can we relate it to n?
The solution key says that "A number with d digits can have a value up to 10^d". Again, no explanation or rationale is provided for this, so we will have to figure it out ourselves.
I think that this is just one of those inherent mathematical properties. Think about the value 10^5 for example. We plug that into Wolf and we get 100000:
Nice.
So.
That's a six-digit number. So a number with 6 digits can have a value up to 10^6 -- but not inclusive! Check this:
no shiz sherlock that's not 6 digits anymore lmao.
But if we just subtract one, we're back to 5 digits. So that's the max number, and we can see that the above property remains true:
cool. Largest 5-digit integer possible, by definition.
So that part makes sense. But we still don't know the runtime.
Well, we just introduced another integer, d, and we need to eliminate it. We now know that the largest possible value for n is 10^d, where d is the number of digits in n. By the properties of logarithms, if n = 10^d, then d = log n.
Let's go back to our original statement -- The runtime is the number of digits in the number, because that's what we're summing. This digit is d. Thus, the runtime is O(d) = O(log n) because we want to express it in terms of n if at all possible.
Well, THAT took forever.
Next:
Ok. First thing we realize with this one is that isInOrder() is of O(s), because it's just a for loop with no special conditions and the functions it calls don't do anything. K. But that's not the full thing.
There is an if-else condition inside of printSortedStrings. If the condition is true (nothing more is remaining), then it
I also think that printSortedStrings(), the one with hardly anything and only one parameter, is the one that's supposed to be called first. It would be nice if they told us that explicitly, though. Well, the else loop has the recursion inside of it, plus it iterates for numChars. So it's O(numChars) plus a little bit more...because it calls printSortedStrings until remaining is 0, and it subtracts 1 every time. So that's basically O(numChars) * O(numRemaining) + O(s), which we can simplify to O(numChars) * O(numRemaining), dropping the lesser added term.
Upon checking the solution key...I'm almost right. The answer is O(kc^k), where k is the length of the string and c is the number of characters in the alphabet. Their k is essentially my s, which we iterate through inside of isInOrder. TO BE CONTINUED...in a future post, I think.
Comments
Post a Comment