Complexity analysis (recursion)?

Hi!!
How you'd analyse functions like this one below?(details please)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//***please ignore the declaration of arguments**//
int insert(arg1(array), arg2(size), arg3(elemnt)){

if (size==0) return 0;

else{

//we call the function
   insert(arg1, size-1, element);
}
}
void insertionSort(array, size){
   if(size>=1{

    insertionSort(array,size-1); // will be executed n-1
    insert(array,size-1,arrayElt); // this function calls itself already above
                          // is this to be considered?
}
}
Last edited on
Roughly:
insertionSort is called n times.
For each invocation of insertionSort, insert gets called too.

Independently, insert will run roughly n times.

Since insert() gets called n times from each of the n invocations of insertionSort(), we get O(n^2).
Thanks a lot for your time and for replying!
Topic archived. No new replies allowed.