Incorporating algorithmic complexity in grading What are some advantages of incorporating algorithmic complexity in grading tests and assignments given to students?

Currently, students in 11th grade at my school are required in tests to write functions that should preform some operation (usually operations on data structures like LinkedList, Stack and Queue). 

This works fairly well in terms of checking whether a student knows how to use those data structures. 

However, it's not uncommon to see an answer that does, eventually, preform the required operation; and yet its complexity is $O(n^3)$ (no kidding. The specific case I'm thinking of is one where the student worked with the unsorted linked list of stacks1 in 3 nested for loops). 

The students are required, after they write their functions, to also write the complexity of their solutions.

In a quest to improve the students' thinking skills, I thought that maybe we should give bonus points if the solutions are inventive and less complex than a head on approach. This means that if a student's function is $O(n)$ for a task that a direct assault would be of $O(n^2)$, they should get more points.

This can also apply to various assignments we can give them, in addition to the tests we already have (or maybe make the tests slightly easier and then add assignments).

The students are in a CS major, and they have experience with java, OOP, Data structures and basic calculations of complexity for various, simple, algorithms)



1We gave them some arbitrary way of comparing stacks (of Integers): The sum of elements.
I wouldn't want to penalize kids who are really relatively inexperienced for not coming up with the fastest solutions on a test. Even if they're in 11th grade and have a couple of years under their belts, they likely haven't been in real situations where run time is important.

If I were to want a specific run time on a test I'd say something like "for full credit make sure your solution runs in $O(blah)$ time." 

If I give an open ended solutions and I don't specify any restrictions on run time, storage limitations, or data set size I tell the kids that I won't penalize them for efficiency unless it's so grossly horrible. For example, if they were to write a sort in their code (and I wouldn't really ask this but it makes for an easy example), I wouldn't penalize a kid for coding an $N^2$ sort even if we covered $n log(n)$ unless I talk about a large data set size. On the other hand if they sorted by say an $N^3$ solution or worse, they would lose some points.

In any event, if you're requiring certain run times you have to be careful that you're not just getting kids to memorize and spit back what the teacher expects.

Also remember that there are plenty of times where a simpler, slower algorithm is both clearer and more than sufficient and that complex fast code that doesn't work isn't nearly as good as simple code that does.

To encourage creativity, give multi level assignments. Create lessons where you can have them develop a solution, see that it's too slow, and then refine it. I do that with finding the mode of a data set (https://cestlaz.github.io/posts/2014-11-17-hidden-complexity.html).

You can also create assignments that encourage this and make test data sets and situations that force kids to work on time efficiency issues.