Data Structure Problem

Dear All

Please help me by giving the solution of the given problem.

Suppose a hospital requires an application to maintain its patient records in a database. The patient records are inserted when the patient gets registered. Each patient has unique registration number (an integer), and a name . Design a Data Structure that allows the dictionary operations with appropriate access time mentioned against each operation
given below:

Record SearchPatientRecord(Registration Number) takes O(1) on average
// This operation searches for the record based on Registration Number and returns that record.

Record SearchPatientRecord(Name) takes O( lg n) on average
// This operation searches for the record based on Registration Number and returns that record.

void insertPatientRecord(Record) takes O( lg n) on average
// This operation inserts the patient record into the database.

void deletePatientRecord(Record) takes O(lg n) on average
// This operation deletes the patient record from the database.
Provide a neat diagram of your data structure design to illustrate these operations.
Outline briefly so that the implementation of these operations should be easily derivable


I Will be highly obliged.
Regards
BALLY

To me this looks like the text of an exam.

Who likes cheaters? Hence, help yourself

Martin

The laughable part is it isn't even a tough problem.

what is means O(log n ) ?

means your searching through a binary tree usually. Or finding a value using recursion.

The previous reply correctly points out that certain algorithms have well known execution "costs." Just in case you were asking what the "O" notation means, this reply contains a simplistic and shallow explaination. I'm not an algorithm person; lots of people will be thrilled to join you in a detailed discussion of algorithm efficiency.

Very briefly:

"Big O" notation is used to discuss an algorithm's efficiency. The statement above means that executing the algorithm under discussion, using a dataset containing "n" items, usually consumes some number of operations on the order of, or roughly the magnitude of, (log n)

For example, to visit each node in a linked list with "n" items, one uses an algorithm that performs roughly "n" "operations".

One refers to it as being or having "O( n )"

I'm running on. Two more quick points:

- You see "operation" in quotes. It's because these discussions are about average times on data distributed in an "average" way. An operaton can be a single instruction or a call into a relational database, and all that implies. People using these terms agree that they're talking about instructions, or comparisons, or transactions, or whatever. As long as you don't compare apples and oranges, it does not matter what an "operation" is.

- Along those lines, a number on the order of, say, 100 can be anything between 100 and 900 - a wide range. The devil is in the details, the special cases and the state of the data.

Finally, anyone is welcome to correct any errors and omissions, but please be kind.

- Chris Brown