So, you have a task to move 3 numbers to the back of an array.
Let's forget that for a moment.
Let's assume you need to take very first number and move it to the end of an array. What the time complexity would be? O(n). Why? That's because you'd need (going to say in simpler words, but not quite exactly what's happening) to take very first value and going step by step starting from the start position to a finish line. Meaning you'd need to go all the distance (array's length) once.
And so think of it you have done it in 5 seconds. So you ran through the distance of n in 5 seconds.
Now, the description says how the algorithm is implemented, "that you take one value at a time...".
So having said that, after you moved 1 element to an end of an array, you need to do the same now with the other first element (it was second in initial setup) - so it takes yet again 5 seconds.
Finally you need to take another first element and move it to the end - yet again 5 seconds.
So you moved 3 elements. m = 3, and n = 5s.
so O(m*n) = 15 s, makes sense, right?
It would be O(n) if you could take all 3 elements at once (check once again in instructions what is said about the used algorithm) and carry them over to the end of an array.
I just probably used N and M interchanged, so really according to an instructions M represents values in an array, while N represents a number of elements to move. I used them otherway round - but that doesn't change the answer, idea is the same.
Campbell, that's just the exam question and not a bad one at that. It illustrates that the base of the logarithm doesn't matter.
Ana, do you know what exactly O(log n) means?
Campbell Ritchie
Marshal
Posts: 66637
251
posted 4 weeks ago
That's what I thought. But in that case surely the time complexity would be logN with the base omitted. After all, logs increase the same way irrespective of their base.
Stephan van Hulst
Saloon Keeper
Posts: 10875
235
posted 4 weeks ago
It doesn't matter. The argument to the O function may be any function. O(log₂ n) and O(log₁₀₀ n) return the same set. It's convention to write complexity classes using the simplest form, but it's not technically incorrect to pass in more information than needed.
Campbell Ritchie
Marshal
Posts: 66637
251
posted 4 weeks ago
Sounds as though we are both thinking the same wway and expressing it differently. Agreed that you can have any base or no base for the log and it is still correct.
Ana Smith
Ranch Hand
Posts: 347
posted 4 weeks ago
Stephan van Hulst wrote:Campbell, that's just the exam question and not a bad one at that. It illustrates that the base of the logarithm doesn't matter.
Ana, do you know what exactly O(log n) means?
I know that it means log base 2 n.
Campbell Ritchie
Marshal
Posts: 66637
251
posted 4 weeks ago
Ana Smith wrote:
Stephan van Hulst wrote:. . . the base of the logarithm doesn't matter.
Ana, do you know what exactly O(log n) means?
I know that it means log base 2 n.
I think you have completely missed the whole point of this discussion.
Stephan van Hulst
Saloon Keeper
Posts: 10875
235
posted 3 weeks ago
Let me rephrase. What does O(n) stand for, what concept does it represent?
Maybe reminding yourself some definition would help to derive to some conclusion.
"The runtime O(f(n)) means that with the growth of n the runtime of the program grows proportionally to fuction f(n)."
Now in a case of Log2(8) and Log100(1000000), we increased n significantly, but how the answer differed?
Answer questions in the post above and you'll know the answer.
Campbell Ritchie
Marshal
Posts: 66637
251
posted 3 weeks ago
Also go back to your older thread; in the case of nlogn complexity, I had a little formula. If you go and change the two instances of log there to log₂ or log₁₀₀ or some other base, and see what the result comes to. You can simplify that formula a bit to matchlogn time complexity
remember the formula from school: Log_a(b) = Log_c(b) / Log_c(a), so Log_a(b) and Log_c(b) differ by a constant factor. See the def of Big_O what that means for O(Log_a) and O(Log_c)
I think in this case it might be helpful to give OP a more direct answer.
The statement in question is true because Big O is about the shape of the curve. That means you can ignore things like constants, e.g., the base of the log.