5 Replies - 389 Views - Last Post: 05 January 2019 - 11:59 AM

#1 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • Posts: 93
  • Joined: 27-December 18

Analysis of Binary Search Algorithm

Posted 05 January 2019 - 09:29 AM

Hi guys!
I'm learning data structure and frankly I have read about binary search in array and I know every thing about its concept. but I'm confused on this, while my array size isn't even then n/2 need to be bounded to upper.bound(n/2) or to down.bound(n/2) (for example 11/2 respectively will be after partitioning 6 or 5) and it will not affect the time complexity! here I stuck in !

In every iteration I will partition my array of size n(assume n is odd) to n/ 2 and if we approximate n/2 to upper.bound(n/2) **assuming that** then we actually added about +1 to the partitioned ratio, I mean with that for example (11/2)+1 , and " +1 " I know asymptotic doesn't matter but what actually confused me it doesn't matter in the iteration itself but In every iteration I do after partitioning "+1" (upper bound of (n/2)) so the constant at the end is accumulated and not simple "+1", i.e after doing all iterations I will get +1+1+1+1+1+1+1 for all the sub-arrayes that I partitioned till I get stop, here we got accumulated constant so we musn't neglect it because it's not simple +1 (constant) it's about sum of, 1+1+1+1+1+1 to all iteration ... and we may get O(n)= n*1 in total...... so why are we neglecting that in time complexity of algorithm??! and we neglect it, why we are neglecting sum of constant? it might be dominant in total, wrong?!

what I understand from what I've read that I can't neglect accumulated constant ...so? :)/>

it would be a pleasure to explain when we neglect the constant and when not ! thanks in advance and thank you for your cooperative.

This post has been edited by macosxnerd101: 05 January 2019 - 02:23 PM
Reason for edit:: Renamed title to be more descriptive. Your topic has nothing to do with a binary search tree.


Is This A Good Question/Topic? 0
  • +

Replies To: Analysis of Binary Search Algorithm

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12491
  • View blog
  • Posts: 45,626
  • Joined: 27-December 08

Re: Analysis of Binary Search Algorithm

Posted 05 January 2019 - 09:36 AM

The floor/ceil issue you mentioned will generate that extra +1 at most log(n) times. So it is absorbed by the log(n) term. That is, the log(n) term is the dominant term. Big-O concerns itself only with the dominant term.

Some useful reading material on Big-O:
https://www.dreaminc...tion-and-big-o/
https://www.dreaminc...nal-complexity/
Was This Post Helpful? 2
  • +
  • -

#3 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • Posts: 93
  • Joined: 27-December 18

Re: Analysis of Binary Search Algorithm

Posted 05 January 2019 - 10:14 AM

I got you .. so what I've claimed +1 +1 +1 +1 is correct and at most we get in total (+1) * logn + O(logn) = O(logn) !

but what about this, lets assume we are dividing the array every iteration by "4" = n/4, which I can say in other words it's the same to say n/2 because the O is absorbing the constant so O(n/4)=O((1/2) *n/2) =O(n/2) and solve the issue by dividing the array by 2 and not by 4, but I feel it's wrong because I changed the given information which at every iteration we must divide by 4 and not by 2 .. and sounds that I missing the concept of neglecting constants .... what's wrong for doing that? instead of the given divider, I put an equal divider in meaning which in my case I used the property of O() for absorbing constant and divide by n/2 because O(n/4)=O((1/2)*n/2)=O(n/2) and then I divide n by 2 ..wrong?! may it formally not correct?!

This post has been edited by RyanMco: 05 January 2019 - 10:17 AM

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12491
  • View blog
  • Posts: 45,626
  • Joined: 27-December 08

Re: Analysis of Binary Search Algorithm

Posted 05 January 2019 - 10:30 AM

You are using the Big-O notation incorrectly. Note that O(n/2) = O(n). We use Big-O notation to describe long-term asymptotic behavior. The constants get absorbed. Please do read the links I posted and make some effort to absorb them.

The binary search algorithm needs at most log(n) + 1 recursive calls. Each recursive call takes a constant number of steps. So the time complexity of binary search is O(log(n)). Note that in the log(n)+1 term, the +1 accounts for cases when n isnít a power of 2.
Was This Post Helpful? 1
  • +
  • -

#5 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • Posts: 93
  • Joined: 27-December 18

Re: Analysis of Binary Search Algorithm

Posted 05 January 2019 - 11:08 AM

View Postmacosxnerd101, on 05 January 2019 - 10:30 AM, said:

You are using the Big-O notation incorrectly. Note that O(n/2) = O(n). We use Big-O notation to describe long-term asymptotic behavior. The constants get absorbed. Please do read the links I posted and make some effort to absorb them.


I have read them frankly but I missed this point !!

so I can't simply say if I have like this T(n)=T(n/4)+C = T((1/2)*(n/2))+c = T(n/2)+c (( here the (1/2) is absorbed inside O() so we can neglect it )) ? thanks for your explanation.

if I can't do like this, why ? is that because O just work on infinity and not in specific?
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12491
  • View blog
  • Posts: 45,626
  • Joined: 27-December 08

Re: Analysis of Binary Search Algorithm

Posted 05 January 2019 - 11:59 AM

Big-O doesnít ďwork like infinity.Ē Note that T(n) is the runtime complexity function. If the input has size n, the algorithm takes T(n) steps. Again, T(n) is a function, and not an asymptotic bound. So T(n/2) is *not* the same as T(n/4).

The point of those tutorials was to introduce you to Big-O in a precise way and provide some basic tools for examining the runtime complexity of iterative algorithms. You donít understand Big-O, which is the foundational concept. And you donít understand how to analyze the precise runtime complexity of an algorithm. So you are mixing these concepts up. Seriously- forget about analyzing algorithms right now. Focus on mastering the concept of the Big-O first.

Can you state the definition of the Big-O? Can you explain it in your own words? Can you examine pairs of functions f(n) and g(n), and identify whether f(n) = O(g(n)) or g(n) = O(f(n))? Can you prove your answers? This should be your starting point, not jumping in the deep end and aimlessly flailing around. I donít know why you are resistant to working carefully through structured material and developing your foundation.
Was This Post Helpful? 4
  • +
  • -

Page 1 of 1