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
7 Years
Discussion Span
Last Post by lillygil

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?

why don't you use if else statement.

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.