- #1

- 55

- 0

please help me to prove that:

O(max(f1(n),f2(n),......,fk(n))) = O(f1(n) + f2(n) + .... + fk(n))

thank you

- Thread starter khdani
- Start date

- #1

- 55

- 0

please help me to prove that:

O(max(f1(n),f2(n),......,fk(n))) = O(f1(n) + f2(n) + .... + fk(n))

thank you

- #2

HallsofIvy

Science Advisor

Homework Helper

- 41,833

- 956

Proof by induction looks like the obvious thing to try.

- #3

- 1,395

- 0

what O meens???

there is some logical error

weird flying robot question

in the first part you mention:

O(max(f1(n),f2(n),......,fk(n)))

i can only guess that the max function returns the maximal value

among the presented functions

on the other hand you say that this maximal value should be equaled to the sum

of all the presented functions in the list.

i think that the only way i t could work

is when all the functions except one are all zeros

you have f1=0 f2=0 ..f15=50 f16=0 etc..

then their sum also equals to the maximal function value.

this whole thing is only a presumption

well i am back to my digital design questions

there is some logical error

weird flying robot question

in the first part you mention:

O(max(f1(n),f2(n),......,fk(n)))

i can only guess that the max function returns the maximal value

among the presented functions

on the other hand you say that this maximal value should be equaled to the sum

of all the presented functions in the list.

i think that the only way i t could work

is when all the functions except one are all zeros

you have f1=0 f2=0 ..f15=50 f16=0 etc..

then their sum also equals to the maximal function value.

this whole thing is only a presumption

well i am back to my digital design questions

Last edited:

- #4

HallsofIvy

Science Advisor

Homework Helper

- 41,833

- 956

The "O" notation refers to the "order" or, for functions of an integer, n, the rate of convergence (or divergence) as n goes to infinity. Saying that O(max(f1(n), f2(n),..)= O(f1(n)+ f2(n)+ ...) says that the sequence formed by choosing a

- #5

- 55

- 0

HallsofIvy, you're right the proof is by induction.

I've used the fact that f1(n)+....+fk(n) <= k*max(f1(n),.....,fk(n)) (proved by induction also), am I on the right route ?

- Replies
- 4

- Views
- 1K

- Last Post

- Replies
- 6

- Views
- 7K

- Last Post

- Replies
- 1

- Views
- 859

- Last Post

- Replies
- 2

- Views
- 1K

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 1K

- Last Post

- Replies
- 17

- Views
- 2K

- Last Post

- Replies
- 7

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 2K