averyrandomguy
Badges: 0
Rep:
?
#1
Report Thread starter 5 years ago
#1
Hi all, I came to this question which I have no idea what it meant to do. It's would be great if anybody can help out here please! I need to know what this program does. It is written in pseudo code. (I'm sorry for the bad layout)
-----------
Input: an integer k >= 0
Output: ??

1) X <- 0
2) Y <- 1
3) for i <- 1 to k do
4) c <- x + y
5) x <- y
6) y <- c
7) return x
--------
Here is my working out, a short explanation of this is if k = 7, the program will loops 7 times until it worked out that x = 13.

k <- 1, 2, 3, 4, 5, 6, 7, 8...
c <- 1, 2, 3, 5, 8, 13, 21, 34...
x <- 1, 1, 2, 3, 5, 8, 13, 21...
y <- 1, 2, 3, 5, 8, 13, 21, 34...

I can see the pattern but I don't know what they represent, does anyone can explain what it is?

Thank you!
0
reply
username2130115
Badges: 16
Rep:
?
#2
Report 5 years ago
#2
it computes the first k terms of the fibonacci sequence and it has exponential complexity.
1
reply
averyrandomguy
Badges: 0
Rep:
?
#3
Report Thread starter 5 years ago
#3
I'll be damn, thanks very much!
0
reply
Jooooshy
Badges: 17
Rep:
?
#4
Report 5 years ago
#4
It loops 1 to k and does a constant amount of work each iteration.. Where did you get exponential from?
1
reply
thecsstudent
Badges: 13
Rep:
?
#5
Report 5 years ago
#5
I think exponential complexity would have applied had it been done recursively and without memoization, in this case it is linear.
0
reply
Smaug123
  • Study Helper
Badges: 15
Rep:
?
#6
Report 5 years ago
#6
Jooooshy is correct. The complexity of the program is linear in input k.
0
reply
username2130115
Badges: 16
Rep:
?
#7
Report 5 years ago
#7
(Original post by thecsstudent)
I think exponential complexity would have applied had it been done recursively and without memoization, in this case it is linear.
(Original post by Jooooshy)
It loops 1 to k and does a constant amount of work each iteration.. Where did you get exponential from?
I think you guys are right; linear complexity for k loops makes sense. I read on stackoverflow that fibonacci has a worst-case complexity of O(2^n) http://stackoverflow.com/questions/3...nacci-sequence.
1
reply
Jooooshy
Badges: 17
Rep:
?
#8
Report 5 years ago
#8
That's a nice answer on SO
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Are you tempted to change your firm university choice on A-level results day?

Yes, I'll try and go to a uni higher up the league tables (42)
27.1%
Yes, there is a uni that I prefer and I'll fit in better (14)
9.03%
No I am happy with my choice (88)
56.77%
I'm using Clearing when I have my exam results (11)
7.1%

Watched Threads

View All