Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
spoiler flag, plz...
I'm afraid I can't give a definitive answer on this point, but I will give you my opinion at least:
Let's say
n
is the size of input array andk
the size of emotion array.If I bound
n = 20 and k = 5
, will you consider this algorithm as a O(1) algorithm?Now what about
n = 10000 and k = 5
? The algorithm hasn't changed and yet it might feel wrong to give it a O(1) complexity: does it became a linear algorithm? just by changing the bounds ofn and k
?And what about
n = 10000 and k = 5000
? Is it still constant? linear maybe? or is it really a quadratic algorithm?Time complexity is here to evaluate an algorithm theorically, the number of elements in an array doesn't matter.
With this algorithm, you make two nested searches in different arrays, so the most precise complexity you can formulate is
O(k * n)
.In my view, as
k
can as big asn
, this is equivalent toO(n²)
.Now, I will amend my previous statement as theory and practice are also two different worlds.
You often hear about amortized time complexity: this notion illustrates precisely how an algorithm can change due to specific constraints such as array size.
As long as
k
is very small comparing ton
, you can say this algorithm is equivalent to a linear algorithm - or even a constant one, but it can be qualified as one only because problem constraints.I think if you try to evalute the time complexity of an algorithm, you do it from the theorical side.
In practice, you don't really judge an algorithm by its time complexity: you often take a simpler algorithm and benchmark it to know if it is efficient or not.
That is the reason why - when talking about algorithm complexity - I tend to give an average case/ worst case complexity rather then an amortized complexity tied to problem constraints.
I write readable solutions sometimes! More seriously, I didn't want to write a quadratic solution for such a task.
But if you really want a short solution, take a look at this one
NB: there is one more character to trim ;-)
Indeed, I admit the scoring function can be quite obscure but you really made an impressively detailed explanation to explicit the algorithm!
Holy moly! I think this fork of yours should be as highlighted as the solution itself, where is the upvote button?!
Let's just discuss your points one by one, would you?
Firstly, question of wheel was discussed with kata's creator and he admit that he ignored it for this kata but not in his second one. I'm not sure you looked it, but all solutions in this other kata have to handle the wheel 1-2-3-4-5.
Secondly, good job on finding that case and I'm pretty sure you can raise an issue with it because it will invalidate a lot of solutions. Anyways, I published a fork of this solution handling it correctly.
Thirdly, last line of your two comments are irrelevant. Yes, a solution to a kata is made to pass the tests. If some tests are missing, as I said above, you should raise an issue to complete them.
And I can't do anything about you not understanding a scoring function. I'm not even sure you tried to. This question has been asked and answered in the comment right under yours.