Hi to all of you! I'm new to this,so I could use a little help!
I've been given some algorithms and I've been asked to find an upper and lower bound of the time complexity of them.
First of all, I would like to know if finding the upper and lower bound means finding the O and Omega time of them.
The algorithms are the following:
1)
int f (int n) {
if n==1
return 1
else return f(n-1)+f(n-1)}
"Assume that adding is Θ(1) time"
2)
int g (int n) {
if n==1
return 1
else x=g(n-1)
return x+x}
"Assume that adding is Θ(1) time"
3)
void f (int n) {
for (i=1; i<= n-1; i++)
for (j=i+1; j<=n; j++)
for (k=1; k<=j; k++)
Some_process_of_O(1)_time}
I'm really interested in learning how to calculate the bounds,not just being given the correct answer. I'll begin with the first one:
If n is equal to 1,then we're done, so the best-time-case is Ω(1), right?
If n isn't equal to 1,two numbers are added within time Θ(1),so the process will continue until some n equal to 1 is found. So, I think that the worst time will be O(n), as it depends on how many numbers will be examined if equal to 1. Am I right?
Thank you in advance! I'll try to find the answer for the rest of the algorithms,too, but here, in Greece, it's already midnight and I must get some sleep in order to get to work tomorrow!