5

So I am reading some code from this website: http://www.geeksforgeeks.org/write-a-c-program-to-find-the-parity-of-an-unsigned-integer/

And it shows how to determine whether a number has even or odd parity. However, I don't understand why the runtime efficiency is log(n). Here is the code for reference:

# include <stdio.h>
# define  bool int

/* Function to get parity of number n. It returns 1
   if n has odd parity, and returns 0 if n has even
   parity */
bool getParity(unsigned int n)
{
    bool parity = 0;
    while (n)
    {
        parity = !parity;
        n      = n & (n - 1);
    }        
    return parity;
}
Kamal
  • 560
  • 1
  • 5
  • 14

2 Answers2

6

The runtime efficiency is O(log(n)), where n is the value of the integer you pass in. However, that's an unconventional way to use O notation.

More frequently, O notation is expressed in terms of the size of the input in bits (the # of bits needed to represent the input), in which case the size of the input is k=O(log2(n)) and the runtime is O(k).

(Even more accurately, the runtime is Θ(s) where s is the number of bits set in n, although that assumes bit operations are O(1)).

nneonneo
  • 171,345
  • 36
  • 312
  • 383
  • So k is the # of total bits or the # of set bits? I'm assuming set bits? – Kamal Jun 20 '15 at 19:10
  • Technically it's O(s) where s is the number of set bits. However, it's worth noting that the algorithm, if extended to arbitrarily large integers, would actually be O(s log n) because bitwise operations are O(log n) on arbitrarily large integers. – nneonneo Jun 20 '15 at 19:18
1

See this So question here

As you see we count no of 1's using this the loop will run exactly the no of bits that are one(1)(let say p) in the binary representation of n.

Thus complexity is Θ(p).

and as the maximum no of bits used to represent n is log2(n) , thus upper asymptotic bound id O(log2(n)).

Community
  • 1
  • 1
cruxion effux
  • 1,054
  • 3
  • 14
  • 27