CODEWITHSUNDEEP
time-complexitybig-o
learner
learner

Reputation: 45

Different big O notation for same calculation(Cracking the coding interview)

In Cracking the Coding Interview, 6th edition, page 6, the amortized time for insertion is explained as:

As we insert elements, we double the capacity when the size of the array is a power of 2. So after X elements, we double the capacity at array sizes 1, 2, 4, 8, 16, ... , X.

That doubling takes, respectively, 1, 2, 4, 8, 16, 32, 64, ... , X copies. What is the sum of 1 + 2 + 4 + 8 + 16 + ... + X?

If you read this sum left to right, it starts with 1 and doubles until it gets to X. If you read right to left, it starts with X and halves until it gets to 1.

What then is the sum of X + X/2 + X/4 + ... + 1? This is roughly 2X. Therefore, X insertions take O( 2X) time. The amortized time for each insertion is O(1).

While for this code snippet(a recursive algorithm), `

int f(int n) { 

  if (n <= 1) {
  return 1;
  }

 return f(n - 1) + f(n - 1); `

The explanation is:

The tree will have depth N. Each node has two children. Therefore, each level will have twice as many calls as the one above it. Therefore,there will be 2^0+ 2^1 + 2^2 + 2^3 + ... + 2^N(which is 2^(N+1) - 1) nodes. . In this case, this gives us O(2^N) .

My question is: In the first case, we have a GP 1+2+4+8...X. In the 2nd case we have the same GP 1+2+4+8..2^N. Why is the sum 2X in one case while it is 2^(N+1)-1 in another.

I think that it might be because we can't represent X as 2^N but I'm not sure.

Upvotes: 1

Views: 82

Answers (1)

patman
patman

Reputation: 34

Because in the second case N is the depth of the tree and not the total number of nodes. It would be 2^N = X, as you already stated.

Upvotes: 1

Related Questions