Landau Notation [closed]

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

开发者_C百科

Closed 7 years ago.

Improve this question

Hy

How do i show the following: f(n) <= f(n-1) + f(n-2)+ .. + f(1) implies f(n) = O(2^n)

I think we can assume that f is monotonically increasing =>

f(n) <= n*f(n-1)

---

Maybe by induction: f(j) <= c*2^(j) for all j < n

Then f(n) <= c(2^(n-2)+2^(n-3) + ... + 2^(1)) <= c*2^(n+1)

What I'm not sure is whether c depends on j, so whether we should write: Then f(n) <= c_(n-2)(2^(n-2)+c_(n-3)2^(n-3) + ... + c_1 2^(1)) <= c*2^(n+1)

---

You were on the right track

f(1) <= f(0)
f(2) <= f(0) + f(1)

|f(2)| <= f(0)|2^2|
|f(1)| <= f(0)|2^1|
|f(0)| <= f(0)|2^0|
Where f(0) is a constant

let x be a constant (equal to f(0))

Suppose that |f(i)| <= x|2^i| for all values of i <= n
Then f(n+1) <= f(n) + (f(n-1) + f(n-2) + ... + f(0))
==> |f(n+1)| <= |f(n)| + |(f(n-1) + f(n-2) + ... + f(0))|
==> |f(n+1)| <= x|2^n| + x|2^n-1| + x|2^n-2| + .. + x
==> |f(n+1)| <= x|2^(n+1)|
so case n implies case n+1

And by induction the claim holds for all n in N

And from the definition of Big-O notation, f(x) is in O(2^n)