Linear runtime possible?

in getFeedback we are asked to implement Linear runtime . However i do think that quadratic runtime is somewhat the fastest we can get, since we have to compare all k chars from one word to the k chars in the other word. Even if we would implement leaving out already CORRECT chars we would needa runtime of k*(k-1)/2 wich also counts as quadratic. Where is my mistake here?

No, in the project presentation, it was stated that if we use for look with a constant as the upper bound, we can consider this to be constant runtime. i < 26 then is to be seen as constant runtime.
The idea is to use another of your implemented functions, I think. And there is only one, that makes sense. :slight_smile:

1 Like

Hi,

it is possible to reach linear runtime. (We don’t give you any challenges which we did not test ourselves.) I am not going to spoil the algorithm here in the forum, because we want you to think about it a bit. :wink:

For example, you can start with the things that @NicoDorn told you and of course take a look at the project presentation slides where some runtime basics are explained. If you then think you need more hints, you could also come the the office hours.

best wishes
Lisa :slight_smile:

One more hint: Do you really have to compare every character in a second, nested loop? How can you avoid looping over both words at the same time?

Best,
Tim

Fun facts: Sorting an array usually takes \mathcal O(n \log n) many operations. In particular, you can even prove that sorting an array of arbitrary data needs at least \mathcal O(n \log n) many comparsions. More on this in your Basic Lecture on Algorithms and Data Structures next semester.

Sometimes, however, you can sort in linear time, i.e. \mathcal O(n) (!). Perhaps you can take inspiration from such algorithms.