Look at the program below. Which of the three functions above (runtime_increment

Question

Look at the program below. Which of the three functions above (runtime_increment, runtime_print and runtime_pow) has the time complexity 'closer' (or more similar) to that of the runtime_rec? Use other methods e.g. look at the actual time it takes to execute for different values of N and see to which function from above). #include #include #include void runtime_rec(int N, char * str){ if (N == 0){ //printf("#s ", str): return: } str[N = 1] = 'L': runtime_rec(N-1, str): str[N-1] = 'R': runtime_rec(N=l, str): } int main(int argc, char** argv) { int N = 0: char ch: char str[100]: printf("run for: N = "): scanf("%d*, &N;): str[N] = '': //to use it as a string of length N. printf("runtime_rec(%d) ", N): runtime_rec (N, str): } Note that since this code uses the math library, if you run it on omega, you will need to link the library at compile time: gcc -o rec train.c -lm and then run it as usual: ./rec Write all your answers in a pdf called hw1.pdf. Make sure you use this exact name.

Explanation / Answer

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <ctime>
using namespace std;
void runtime_rec(int N, char * str)
{
if(N==0)
{
return;
}
str[N-1] = 'L';
runtime_rec(N-1, str);
str[N-1] = 'R';
runtime_rec(N-1, str);
}
int main (int argc, char** argv)
{
clock_t start, end;
float sec;
start = clock();
int N = 0;
char ch;
char str[100];
printf(" run for: N = ");
scanf("%d", &N);
str[N] = '';
printf(" runtime_rec(%d)",N);
runtime_rec(N,str);
end = clock();
sec = (((float) (end - start)) * 1000) / CLOCKS_PER_SEC;
printf(" Actual Execution Time = %F", sec);
}
OUTPUT
run for: N = 0
runtime_rec(0)

Actual Execution Time = 0.051000

run for: N = 1
runtime_rec(1)
Actual Execution Time = 0.057000
run for: N = 2
runtime_rec(2)

Actual Execution Time = 0.049000
run for: N = 3
runtime_rec(3)
Actual Execution Time = 0.050000

run for: N = 4
runtime_rec(4)
Actual Execution Time = 0.079000

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.