One good overall educational strategy is to teach the same thing to students repeatedly, using a Spiral approach, in which each turn of the spiral teaches at a deeper level. Don't expect the students to completely get much of anything at the first mention of it, but reinforce the ideas and deepen the knowledge. You can do this for many things in one course, but you can also do it over a student's career.
As you say, it is a mathematical concept and students may not yet have the tools needed to completely get it, but you can start, and you can give them enough insight so that when
Big O comes up later, say in their undergraduate education, they have some prior basis for understanding it more deeply.
However, it is important that you don't oversimplify the topic or to give them false information, leading them to misconceptions that require un-learning later. So, first, be honest: the topic is mathematical, it is a bit deep, we can only scratch the surface a bit.
For young students without a solid algebra background and little exposure to calculus, it might be good to start with a graphing calculator so that students can see what happens to common functions as the independent variable increases. Graphing $log(x)$, $x$, $x^2$, $2^x$ etc is a start. Graphing $1000x + x^2$ can give them the idea that the high order term dominates the growth. If they can see it, you don't need to depend on their knowledge from elsewhere.
Next, you can show them a few algorithms and look at the actual run times, noting that you are only giving them an idea. One of my favorite "tricks" is to ask students who have seen a few sort algorithms, to come up with the most inefficient sort algorithm they can think of. With a good randomizer even repeatedly randomizing an array and then checking to see if it is sorted is an algorithm by the law of large numbers. If they know about permutations they can even calculate the maximum number of iterations needed to sort. If they are not likely to know that from other places, then computing permutations can be an earlier programming exercise.
The problem with teaching the first cycle of a deep knowledge of Big O is that it is easy to give the wrong impression about a lot of things depending on the words and examples you use. If you say that, for example, bubble sort is $O(n^2)$ you are correct, but it may have little meaning. It doesn't mean, however that the "running time" of bubble sort is $n^2$, but (if $n^2$ is the best bound) that it is "proportional to $n^2$ for large values of n." It is easy to forget to say those extra words: "proportional", "large...". It is also easy to forget that Big O is about upper bounds, only. So technically, Bubble Sort is also $O(2^n)$, but it would probably not be wise to stress that in the first cycle of learning outside a mathematics class.
Also, the examples matter. Bubble sort (if unoptimized) always runs in quadratic time and you can see that from the algorithm. It depends only on the size of the data set. But insertion sort is different. The normal program has two nested loops, just like bubble sort, but if the original dataset is already nearly sorted (by some measure of "nearly") then it actually runs in near linear time - or even linear time, for some examples. But it is still a quadratic algorithm, since its worst case behavior is quadratic. So, "worst case" is another important word to keep emphasizing.
You also need to mention, but probably not stress, is that efficiency need not be determined by the size of the data set necessarily. Factoring large numbers is an example. There is only one number to factor, but it is harder to do for larger numbers since (for brute force, anyway), the difficulty is determined by the number of possible solutions, which is itself large (but can be estimated).
A third complication is that it isn't always time complexity that is needed. Space complexity is also often important. How much "scratch" space does an algorithm need for datasets of different sizes (or datasets of different complexity, or ...). A recent (early 2018) experiment(pdf) in Artificial Intelligence, pitted two different AIs against one another. One of them "learned" that it could "win" the competition by forcing the other to use more and more memory space, resulting in a crash of the other.
Another idea to get across is that if the numbers (data set size for example) are small, then using a highly efficient algorithm may be worse than one theoretically more "inefficient".
Big O is about asymptotic behavior, of course and the more efficient algorithm may be more complex and actually be worse on small data sets as well as being, perhaps, more likely to be buggy. Some quick sorters, for example, revert to a quadratic algorithm once the split gets the datasets small enough. I once built a product that had an exponential algorithm embedded in it. That worked, since the likelihood of a large dataset was vanishingly small. Integer Programming is actually done by real programs in the real world in spite of the complexity of the problem itself.
Finally you need to note that
Big O is about algorithms. That is related to the complexity of problems, but isn't exactly the same thing. There are a lot of array sorting algorithms and they have different exponential behavior. But the problem itself has an inherent complexity. For sorting
long values (the built in data types) in a computer, the complexity is actually linear (Radix Sort). You need some sort of a BigNum data type before you reach $O(n*log(n))$, since the number of possible values in int is bounded. And for large numbers of arbitrarily large values, you start to run into space problems for most purposes.
Let me note, for completeness, prompted by a "conversation" in comments here with user RiaD, that any algorithm that is $O(n^2)$, such as Bubble Sort, is also $O(n^3)$ and $O(n^4)$ and $O(2^n)$, since all of those other functions dominate $g(n) = n^2$. One normally gives a "good" estimate, but the "worse" estimates for growth apply by default.
tl;dr: Say what's true. It is a complex, mathematical topic. Examples are good. Deep understanding can come later. Completeness isn't essential in the first cycle of understanding. Take that into account when testing.