# A Simple C Question

Status
Not open for further replies.

#### Ecko

##### Wandering In Tecno Land
We'll a very simple C question here related with data structures

I want to know if Binary Search can be done in Linked List
An explanation will be highly appreciated

#### iq6886

##### Broken In
Yes Binary search can be done using linked list...

but we simply don't coz the complexity of binary search using linked list is O(nlgn) and not O(lgn ) as in arrays..
let me explain you why this..

basically the increase in complexity is because of the added complexity to seeking to any element which is constant when using array( when we need to reach middle we just index it in array , but in linked list we need to reach it by traversing the linked list ).

so we need to tranverse linked list for every step of binary search or log n times.

I guess i explained it properly enough....

OP

#### Ecko

##### Wandering In Tecno Land
Thanx a lot dude
Got it
BTW what's this
the complexity of binary search using linked list is O(nlgn) and not O(lgn ) as in arrays..

#### Faun

##### Wahahaha~!
Staff member
that big O notation Scary stuff, not anymore.

#### srinivasa.s

##### Right off the assembly line
How is the complexity (n log n)? Its still linear - O(n). The worst case complexity of even linear search is O(n). This cannot be any worse! Basically, the search will not be called "binary search" if its done on lists

#### iq6886

##### Broken In
^ it will still be called binary search beacoz of the concept whtr done using arrays or linked list or any other data type of ur choice..

and about the complexity , you can easily find it out to be O(nlgn) by solving the equation
T(n)=T(n/2) + O(n) ( not so sure about the equation though.. need to chk tht)

Status
Not open for further replies.