CODEWITHSUNDEEP
algorithmtime-complexityavl-tree
Nadav Matityahu
Nadav Matityahu

Reputation: 11

calculating the time complexity of an AVL tree algorithm

I'm looking to calulate the time complexity of the following algorithm. I have an AVL tree and a pair of two numbers (x,y) such that x<y. The algorithm's purpose is to print all numbers in the tree between x and y. x and y are definitly not in the tree.

My goal is to make an algorithm whose runtime is O(logn + k) such that k is the number of nodes between x and y and n is the total number of nodes in the tree.

my algorithm is this:

A function that receives x and y, starts from the root of the tree and goes like this:

if the current node is between x and y - print it and recursively call the left node with (x,current node value) and the right node with (current node value,y).

if the current node is smaller than x - call the right node recursivley with (x,y)

if the current node is bigger than y - call the left node recursivley with (x,y) The function stops when it reaches a leaf(node who has no other nodes attached to it). Does my function meet the runtime requirement?

Upvotes: 1

Views: 1205

Answers (1)

Gene
Gene

Reputation: 46990

Yes it does. You can prove it by noting that your algorithm does nothing but visit nodes, and every node visit requires O(1) time. Each visit that discovers a value in the range can be "charged" to the O(k) part of the time bound.

But there are some visits - those that find nodes less than or greater than the range - that don't discover a value. These must be "charged" to the O(log n) part of the time bound.

The rest of the proof is to show that there are indeed no more than O(log n) such visits. The key is to show there can be at most a constant number c of them at each depth from the root. This requires some reasoning about the structure of BSTs. I'll let you have the fun of working out the details. There are O(log n) depths, so the number of these visits is O(c log n) = O(log n). qed

Additional note

Your algorithm needlessly shuffles the values. It's easy to tweak so that values are discovered in sorted order. Again I'll let you work out the details.

Upvotes: 1

Related Questions