Calculate the Depth of the recursive algorithm

  • Thread starter Thread starter tsgiannis
  • Start date Start date
  • Tags Tags
    Algorithm Depth
Click For Summary
SUMMARY

The discussion centers on calculating the depth of recursion for a specific algorithm that sums elements of an array using a divide-and-conquer approach. The algorithm, defined as sum(A, left, right), recursively divides the array into halves until it reaches base cases. For an array of size n that is a power of 2, the depth of recursion can be determined by analyzing the number of times the array can be halved before reaching individual elements. The key insight is that the depth of recursion is log2(n), where n is the number of elements in the array.

PREREQUISITES
  • Understanding of recursive algorithms
  • Familiarity with divide-and-conquer strategies
  • Basic knowledge of logarithmic functions
  • Experience with pseudocode interpretation
NEXT STEPS
  • Study the concept of recursion in algorithms
  • Learn about divide-and-conquer algorithms in detail
  • Explore logarithmic time complexity and its implications
  • Practice writing and analyzing recursive functions in a programming language
USEFUL FOR

Students studying algorithms, computer science enthusiasts, and anyone interested in understanding recursion and its applications in programming.

tsgiannis
Messages
1
Reaction score
0

Homework Statement


Hello to everybody
I have this homework and my main issue is that is cannot find any bibliography to read that does what my homework requires.
The problem goes like
We have this recursive algorithm that calculates the sum of an array elements from array element k to array element n

procedure sum(A, left, right)
if left ? right then
if left = right then return(A
);
else return(0);
mid := [(left + right) / 2];
x := sum(A, left, mid);
y := sum(A, mid+1, right);
return(x + y);
The problem goes like this
If the array A has n elements that are an expression of 2 (like 8 = 2^3) find the depth of recursion for the call of the procedre sum(A,1,n)

I don't ask for the solution but just a helping hand to find some relative material.

Homework Equations





The Attempt at a Solution

​
 
Physics news on Phys.org
I've never seen that language before, so I don't know what is going on in your code at all. If I were you, I'd probably run through the algorithm by hand for n = 1, 2, 4 and by then, a pattern will probably develop. Then, use that pattern to derive the general rule for depth.
 

Similar threads

Comp Sci How do I think about recursion in programming?
  • · Replies 11 ·
Replies
11
Views
2K
Algorithm for computing the depths of all the nodes of tree
  • · Replies 1 ·
Replies
1
Views
3K
Find p in a Sorted Array with Unique Property | O(log n) Algorithm
  • · Replies 5 ·
Replies
5
Views
2K
Monte Carlo simulation, rejection algorithm
  • · Replies 2 ·
Replies
2
Views
3K
Comp Sci Complexity for generating strings of length k from CNF grammar
  • · Replies 3 ·
Replies
3
Views
2K
Runtime of the line where a recursive call happens = ?
  • · Replies 10 ·
Replies
10
Views
2K
Comp Sci Recursive Double code to Calculate the sum of the square roots <= a number
  • · Replies 19 ·
Replies
19
Views
3K
C data structures and algorithms - graph problem
  • · Replies 2 ·
Replies
2
Views
2K
Evaluate the complexity of this graph coloring algorithm
  • · Replies 1 ·
Replies
1
Views
2K
Proof of optimality of algorithm
  • · Replies 9 ·
Replies
9
Views
2K