0
$\begingroup$

Maybe the title is bad format but, I want to ask if is possible proof the Segment Tree complexity with the recursion tree.

In other words I'm making a simple report on segment tree and I want to try to prove with a simple image that the complexity time on each query is O(log N), so to do that I make a simple assertion that if the merge sort complexity is O(N log N) so sort the array, I can say that to traverse only one part of the tree I need only O(log N) time.

And the image that I choose to prove that is the recursion, like the tree below.

enter image description here

I will post also what I'm trying to explain inside the report and maybe there is some different idea to prove that.

enter image description here

p.s: Sorry for the error inside the report image but it is without spell check and I'm a person with a dyslexia problem

Improve this question
$\endgroup$
5
  • $\begingroup$ I think it's easier to prove that at each level there are at most 2 nodes where you recursively call the query. That being sad, your image would have O(1) as the cost per level which in total adds up to O(logN) $\endgroup$ – VashTheStampede Jan 11 at 23:35
  • $\begingroup$ Thanks you, do you think that it is not interesting the recursive tree? $\endgroup$ – vincenzopalazzo Jan 11 at 23:37
  • 1
    $\begingroup$ Honestly I don't think that Segment Trees provide a good "recursive tree" argument for their complexity (but I'm always open to read some). It seems you are trying to write some report for an Algorithms university project (or something similar), hence I think that first and foremost it is important to be clear and concise :) $\endgroup$ – VashTheStampede Jan 11 at 23:42
  • $\begingroup$ You have right :-D thanks $\endgroup$ – vincenzopalazzo Jan 11 at 23:43
  • $\begingroup$ it is a university report, yes but it is a personal interest to implement data structure and understand how they works $\endgroup$ – vincenzopalazzo Jan 11 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.