0

What's a good strategy to determine the running time (Big O notation) of data structures and algorithms. I have the following to figure out the running times for and I'm having trouble determining what it would be.

AINC is an array containing n integers arranged in increasing order.

AD is an array containing n integers arranged in decreasing order.

AR is an array containing n integers in random order.

Q is a queue implemented as a linked list and containing p elements.

LINK is a linked list containing n nodes.

CIRC is a circular linked list containing n elements, where C points to the last element.

T is a binary search tree containing n nodes.

a) Searching for an element in AINC using linear search.

b) Deleting the 10thnode of linked list LINK.

c) Calling a function which uses Q, and calls dequeue m times.

d) Inserting an element at the end of the list CIRC.

e) Deleting the last element of CIRC.

f) Finding the largest element of T.

g) Determining the height of T.

h) Making the call selectionsort (AINC, n).

i) Making two calls one after another. The first call is mergesort(AD,n), followed by the call insertionsort(AD,n).

j) Converting a decimal integer num into its binary equivalent.

***This is not hw. I am preparing for an exam.

Improve this question
19
  • 1
    Please tell me this is homework? Commented Dec 14, 2010 at 16:07
  • nope im studying for an exam. Commented Dec 14, 2010 at 16:09
  • @Krysten big difference indeed Commented Dec 14, 2010 at 16:11
  • Is that your homework?, If yes u have to do it yourself, If No then share your answers and lets discuss them. Commented Dec 14, 2010 at 16:13
  • ಠ_ಠ This is bad. You should feel bad. Commented Dec 14, 2010 at 16:14

2 Answers 2

Reset to default
2

(Since the OP asked for it)

You pick up a piece of paper.

  • If your question mentions a number (e.g. repeat n times, or find the n-th last element):

You perform by hand on paper the operations needed to perform the mentioned action when that number is 1 (if applicable).

You repeat for each of the following values of that number: 2, 10, 20, 100, 1000 and 10000. Just for kicks you can also try with the actual number mentioned in the question.

You measure the time it took you for each case and then you plot on a piece of paper (oh, a spreadsheed would also do, I suppose) the function t(n), where t is the time, and n the number.

You look through your old math books to identify the curve. E.g. if it's a parabol, you most probably have an O(n^2) algorithm in your hands.

  • If your question does not mention a number:

Repeat the previous procedure above by using 2, 10, 20, 100, 1000 and 10000 elements in any data structure mentioned (array, list etc). If the "structure" is a number, just use that many digits.

NOTE:

If you manage to visualise the procedure above without turning half of this planet's remaining trees into paper or having your hand fall off, then you are half-way towards a semi-decent intuitive technique.

You should read up on the proper mathematical way to deal with this, though - intuition can only take you so far in this case.

Additionally, most of the examples that you mentioned are so basic that most people just memorize (and a bit later they just know) their complexities. You should really get a book or some decent notes on this. Introduction to Algorithms is a nice, big fat introductory book on this field.

EDIT:

Searching for algorithms and complexity in Google also produces a whole pile of interesting results. You should try it once in a while...

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

If you are new to Big O analysis and have some time (2.5 hours), I would recommend watching the first two lectures of this algorithms class delivered by Leiserson himself.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.