Maximum Rule

  • Thread starter khdani
  • Start date
  • #1
55
0
Hello,
please help me to prove that:
O(max(f1(n),f2(n),......,fk(n))) = O(f1(n) + f2(n) + .... + fk(n))

thank you
 

Answers and Replies

  • #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
 
Last edited:
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,833
956
If you do not understand a notation, just ask about it and assume that what other people are saying is wrong!

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 ai the largest of f1(i), f2(i), ..., converges (or diverges) as fast as the sequence an= sum of f1(n)+ f2(n)+ ....
 
  • #5
55
0
'O' is the 'Big Oh' notation in complexity theory.

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 ?
 

Related Threads on Maximum Rule

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
Top