def dividing(n):
while n!=1:
n=math.floor(n/2)
return True
There's that code, my initial thought is that it just has a complexity of n since it n is just the input, no squares no anything but when researching about n/2, I found out that it's Big-O complexity is Log(m), so now im confused, is the big-o complexity of this is log(m)? If yes, why is that so?
Let's assume we count everything within the scope of the while loop as a basic operation.
while(invariant) { basic-operation }
Then, to find an upper asymptotic bound for the number of basic operations of the dividing function, we need an upper bound on, given an input n to the function, how many times the while loop executes.
We may simple reverse the loop and it will become quite apparent (ignore the flooring):
// The value of 'n' until termination of
// the while loop, in reverse (n here == n_start)
1 + 2 + 4 + ... + n
= 2^0 + 2^1 + 2^2 + ... + 2^(log2(n))
= sum_{i=0}^{i=log2(n_start)} 2^i
The sum expression runs i, which in our context is the loop variable, from 0 to log2(n) by steps of 1, meaning the while loop runs (ignoring flooring) log2(n) + 1 times, in turn meaning that O(log2(n)) provides an upper asymptotic bound for the time complexity of your function.
In this kind of situation, where the input is a single number, we cannot assume that arithmetic operations take constant time. Formally, the "input size" of the algorithm should be measured in bits, and it takes more time to divide a number that takes more bits to represent.
Your code actually works with floating-point numbers, which means the actual magnitude of the number is not directly related to the number of bits required to represent it (and we will have to ignore that real floating-point numbers have a fixed size in bits, otherwise the concepts of "input size" and "time complexity" simply make no sense). It is simpler to analyse a similar algorithm which works on integers; let's instead say the algorithm takes an integer and does n = n // 2 or n = n >> 1 instead of n = math.floor(n / 2). An integer n takes O(log n) bits to represent.
The actual amount of time depends on the algorithm used to perform the division; we can say that the time complexity is O(D(n) log n) where D(n) is the time complexity of the division algorithm. There are various division algorithms with different time complexities, which also depend on the time complexity of the multiplication algorithm used. On the other hand, since dividing by 2 is equivalent to a right-shift by 1 bit, if we write the algorithm to use a bit-shift (or if the division algorithm optimises it to a bit-shift in this special case), we will have D(n) = O(log n) because bit-shifting takes linear time in the number of bits. In that case, the original algorithm's time complexity would be O(log^2 n).