I cannot figure out what is more computationally efficient between the two representations mentioned in my question in terms of training time and the amount of data required. Especially, when it comes to considering the order of the words in a sentence.
Neither of these approaches really represent the word order, though it could be argued that a bag of n-grams has some word order representation in it.
Remember that, using bag of words, each word is assigned a value and then the aggregate values are converted into a multi-hot encoded row vector. In other words, a sentence like:
This is a test.
Would likely be preprocessed to:
this is a test
And then converted to a numeric representation:
[15, 12, 3, 56]
where each of the numbers is the number used to encode or tokenize that word. The next step would be to convert this to a multi-hot encoded vector:
[ 0, 0, 0, 0, ..., 1, 0, 0, 1, 0, 0, ...]
where the length of the vector is the length of the number of words in the vocabulary.
As a result of this representation, all information about word order is lost.
Now consider the case of bag of n-grams. Let's assume we used an $n=3$ for the number of n-grams. This means that, rather than tokenizing each word individually, we are now converting each trio of words into a token. These tokens are then, again, converted to a multi-hot encoded vector.
While it is certainly true that there is some word order information retained within the n-grams themselves, the order of the n-grams in the text is still lost when we convert to the multi-hot encoded vector.
Bag of words preserves no word order at all, so the computational efficiency with regard to that is non-existent. Bag of n-grams preserves some word order, but not much. Bag of n-grams is certainly an easy thing to implement, especially with variable length inputs, so in that sense it might be more efficient to use over other approaches, such as a transformer, LSTM, or an embedding layer with a Conv1D.