0

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!

2
Contributors
2
Replies
3
Views
6 Years
Discussion Span
Last Post by lillygil
0

As for the second algorithm, I think that it has the same best and worst case running-time as the first one...
For the third algorithm,my thought is that I have 3 if's. All of them are related to n ,directly or not, so I think that best and worst case running time is the same, that is Θ(n^3)...

Could anyone please tell me which of the above are correct and which aren't?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.