Time complexity

Source

What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2.

?

void fun() { int i, j; for (i=1; i<=n; i++) for (j=1; j<=log(i); j++) printf("GeeksforGeeks"); }

Program to count number of set bits in an (big) array

Source

Interesting part of the solution is to see how the look up table is formed

    0, 1, 2, 3  0 - 0, 1, 1, 2 -------- GROUP_A(0)

 4 - 1, 2, 2, 3 -------- GROUP_A(1)

16 - 1, 2, 2, 3 -------- GROUP_A(1)

20 - 2, 3, 3, 4 -------- GROUP_A(2)

 8 - 1, 2, 2, 3 -------- GROUP_A(1)

12 - 2, 3, 3, 4 -------- GROUP_A(2)

24 - 2, 3, 3, 4 -------- GROUP_A(2)

28 - 3, 4, 4, 5 -------- GROUP_A(3) ... so on

A binary tree problem - Populating next right pointers in each node

Source

void connect(Node* p) {

if (p == NULL)

return;

if (p->leftChild == NULL || p->rightChild == NULL)

return;

Node* rightSibling;

Node* p1 = p;

while (p1) {

if (p1->nextRight)

rightSibling = p1->nextRight->leftChild;

else

rightSibling = NULL;

p1->leftChild->nextRight = p1->rightChild;

p1->rightChild->nextRight = rightSibling;

p1 = p1->nextRight;

}

connect(p->leftChild);

}