KEMBAR78
Time Complexity of Binary Search | PDF | Science & Mathematics
Scribd
Upload
97 views1 page

Time Complexity of Binary Search

The document explains the time complexity of Binary Search, demonstrating that the length of the array is halved with each iteration. After k iterations, the length of the array becomes 1, leading to the equation n = 2^k. Consequently, applying logarithmic functions reveals that the time complexity of Binary Search is O(log2(n)).

Uploaded by

Sayani Chandra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
97 views1 page

Time Complexity of Binary Search

The document explains the time complexity of Binary Search, demonstrating that the length of the array is halved with each iteration. After k iterations, the length of the array becomes 1, leading to the equation n = 2^k. Consequently, applying logarithmic functions reveals that the time complexity of Binary Search is O(log2(n)).

Uploaded by

Sayani Chandra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Calculating Time complexity of Binary Search:

• Let say the iteration in Binary Search terminates after k iterations.


• At each iteration, the array is divided by half. So, let’s say the length of array at any
iteration is n
• At Iteration 1,
Length of array = n

• At Iteration 2,
Length of array = n⁄2

• At Iteration 3,
Length of array = (n⁄2) ⁄ 2 = n⁄22

• Therefore, after Iteration k,


Length of array = n⁄2k

• Also, we know that after


After k divisions, the length of array becomes 1

• Therefore
Length of array = n⁄2k = 1
=> n = 2k

• Applying log function on both sides:


=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)

• As (loga (a) = 1)
Therefore,
=> k = log2 (n)

Hence, the time complexity of Binary Search is


log2 (n)

You might also like