What is the complexity of the below program?

What is the complexity of the below program? I think it must be O(n), since there is a for loop that runs for n times.

It is a program to reverse the bits in a given integer.

unsigned int reverseBits(unsigned int num)
{
    unsigned int NO_OF_BITS = sizeof(num) * 8;
    unsigned int reverse_num = 0;
    int i;
    for (i = 0; i < NO_OF_BITS; i++)
    {
        if((num & (1 << i)))
           reverse_num |= 1 << ((NO_OF_BITS - 1) - i);
    }
    return reverse_num;
}

What is the complexity of the above program and how? Someone said that the actual complexity is O(log n), but I can't see开发者_如何学Python why.

Considering your above program, the complexity is O(1) because 8 * sizeof(unsigned int) is a constant. Your program will always run in constant time.

However if n is bound to NO_OF_BITS and you make that number an algorithm parameter (which is not the case), then the complexity will be O(n).

Note that with n bits the maximal value possible for num is 2^n, and that in this case if you want to express the complexity as a function of the maximal value allowed for num, the complexity is O(log₂(n)) or O(log(N)).

O-notation describes how the time or space requirements for an algorithm depend on the size of the input (denoted n), in the limit as n becomes very large. The input size is the number of bits required to represent the input, not the range of values that those bits can represent.

(Formally, describing an algorithm with running time t(n) as O(f(n)) means that there is some size N and some constant C for which t(n) <= C*f(n) for all n > N).

This algorithm does a fixed amount of work for each input bit, so the time complexity is O(n). It uses a working space, reverse_num, of the same size as the input (plus some asymptotically smaller variables), so the space complexity is also O(n).

This particular implementation imposes a limit on the input size, and therefore a fixed upper bound on the time and space requirements. This does not mean that the algorithm is O(1), as some answers say. O-notation describes the algorithm, not any particular implementation, and is meaningless if you place an upper bound on the input size.

if n==num, complexity is constant O(1) as the loop always runs fixed number of times. The space complexity is also O(1) as it does not depend on the input

If n is the input number, then NO_OF_BITS is O(log n) (think about it: to represent a binary number n, you need about log2(n) bits).

EDIT: Let me clarify, in the light of other responses and comments.

First, let n be the input number (num). It's important to clarify this because if we consider n to be NO_OF_BITS instead, we get a different answer!

The algorithm is conceptually O(log n). We need to reverse the bits of n. There are O(log n) bits needed to represent the number n, and reversing the bits involves a constant amount of work for each bit; hence the complexity is O(log n).

Now, in reality, built-in types in C cannot represent integers of arbitrary size. In particular, in this implementation uses unsigned int to represent the input, and this type is limited to a fixed number of bits (32 on most systems). Moreover, rather than just going through as many bits as necessary (from the lowest-order bit to the higher-order bit which is 1), this implementation chooses to go through all 32 bits. Since 32 is a constant, this implementation technically runs in O(1) time.

Nonetheless, the algorithm in conceptually O(log n), in the sense that if the input was 2^5, 5 iterations would be sufficient, if the input was 2^10, 10 iterations would be sufficient, and if there were no limit on the range of numbers an unsinged int would represent and the input was 2^1000, then 1000 iterations would be necessary.

Under no circumstances is this algorithm O(n) (unless we define n to be NO_OF_BITS, in which case it is).

You need to be clear what n is. If n is num then of course your code is O(log n) as NO_OF_BITS ~= log_2(n) * 8.

Also, as you are dealing with fixed size values, the whole thing is O(1). Of course, if you are viewing this as a more general concept and are likely to extend it, then feel free to think of it as O(log n) in the more general context where you intend to extend it beyond fixed bit numbers.