Complexity in algorithms

I got the following algorithm and I am trying to figure out the complexity of it if i call max(a,1,n):

max(a,i,n)
if i<n then x=max(a,i+1,n)
       else return(a[n])
if x<a[i] then return(x)
          else return(a[i])
desperadoAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

nietodCommented:
We cannot provide answers to school assignments.  That is grounds for removal from this site.  (for both you and the experts involved.)  We can provide only limitied help in accademic assignments.    We can answer specific (direct) questions, like you might ask your teacher.  We can review your work and post suggestions, again, like your teacher might do.

Do you have specific questions?
Do you have any work on this (incomplete even) that we can review?



I can tell you this much, the duration of the algorithm is proportional to the number of times it calls itself recusrively.  So you need to figure out how many times the function calls itself.

i.e you will have a formula based on a, i, and n (it is possible that 1 or 2 of these might not appear in the formula) that tells you how many times max() will be called.
0
desperadoAuthor Commented:
I read the license agreement here. I posted the question like it is because it is not an assigment. I'm learning complexity by myself.
0
desperadoAuthor Commented:
The work i have is the algorithm that is posted in the question. I aslo made this program to test if the algorithm worked. It does get the maximum:

#include<iostream.h>
int max(int [],int,int);
main()
{
 int a[5]={200,10,100,6,8};
 int maxi;
 maxi=max(a,0,4);
 cout<<"The maximum is:"<<maxi;
 return(0);
}

/*function founds the maximum number and returns it.Funtion goes through all the elements in the array and then compares them to find maximum.*/

max(int a[],int i,int n)
{
 int x;
 if(i<=n)
 { x=max(a,i+1,n);
 }
 else
 {
      return(a[n]);
 }
 if(x>a[i])
 {
      return(x);
 }
 else
      return(a[i]);
}

0
AdihCommented:
its theta of n.
t(n)=t(n-1) + theta(1)
by re-insertions u can see its the theta of n.

adi.
0
nietodCommented:
The key is to lool at the algorithm in terms of the work it does.  The real work occurs when the algorithm has to call itself again recursively.  So
the algorithm, has the form

max(int a[],int i,int n)
{
   int x;
   if(i<=n)
   {
        x=max(a,i+1,n);  // The real work.
   }
   return something
}

(Take a look, after that recusive call, the algorithm just quickly returns a value in one of three ways, that is pretty fast, the slow part is calling itself again and again...)

So the question is, give particular values of i and n, how many times does it call itself recursively?  Well, i starts out as the  "low value" and one each call it increases by 1 until it reaches the "high value" (n).  So you can see the function will be called recursively n-i+1 times.

so the function is O(n-i+1)  which is pretty close to O(n-i).

This makes it a linear function, that is its run-time duration is linearly propotional tot he amount of data it must process.  Double the data (double n and leave i 0) and the process takes twice as long...)

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.