So i’m till now hasnt been able to figure out how to make the running time linear. as for the wrongpos. i need always atleast double for loop. can i get some hints as how to make it linear?

You can use the magnifier symbol in the top right to search for topics:

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.
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 …
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.
If you have something like this:
for(int i = 0; i < constant; i++){
for(int j = 0; j < length(input); j++){
<do something in constant time>
}
}
Then your program has constant\cdot \mathcal{O}(length(input)) = \mathcal{O}(length(input)) runtime, which is indeed linear.
Tip zero would be to ignore the formal specification. It will not guide you towards an efficient algorithm
Tip one would be to come up with two rather large (ie 10 to 15 character) words on paper, noting intermediary results, and trying to figure out the correct result. A working implementation (even if it is too slow) might help you double-check the on-paper results, to ensure that you know what you are doing.
If you do this often enough, you can maybe see some pattern you…
1 Like