I am unsure how to formally prove the Big O Rule of Sums, i.e.:

```
f1(n) + f2(n) is O(max(g1(n)),g2(n))
```

So far, I have supposed the following in my effort:

Let there be two constants `c1`

and `c2`

such that `c2 > c1`

. By Big O definition:

```
f1(n) <= c1g1(n) and f2(n) <= c2g2(n)
```

Can anyone advise how I should proceed? Is it reasonable to introduce numerical substitutions for the variables at this step to prove the relationship? Not knowing `g`

or `f`

, that is the only way I can think to approach.

Any help would be greatly appreciated.

You don't even need the definition - just divide both sides by the faster-growing function, take the limit in infinity, and the slower-growing function will approach zero (i. e. it's insignificant).

Let

```
gmax = max(g1, g2), and gmin = min(g1, g2).
```

gmin is O(gmax). Now, using the definition:

```
gmin(n) <= c*gmax(n) for n > some k
```

Adding gmax(n) to each side gives:

```
gmin(n) + gmax(n) <= c*gmax(n) + gmax(n) for n > some k
gmin(n) + gmax(n) <= (c+1)*gmax(n) for n > some k
g1(n) + g2(n) <= c'*gmax(n) for n > some k
```

So we have g1+g2 is O(max(g1, g2)).

Since f1+f2 is O(g1+g2), the transitive property of big-O gives us f1+f2 is O(max(g1, g2)). QED.

I suppose I might be more of a constructivist, I'd attack the problem like this:

By the definition of Big-O, there exist positive c_{1}, c_{2}, N_{1}, and N_{2} such that

f

_{1}(n) <= c_{1}g_{1}(n) for all n > N_{1}and

f

_{2}(n) <= c_{2}g_{2}(n) for all n > N_{2}

Let:

N' = max(N

_{1},N_{2})

c' = c_{1}+ c_{2}

g'(n) = max(g_{1}(n),g_{2}(n))

Then for all n > N' we have:

f

_{1}(n) <= c_{1}g_{1}(n) <= c_{1}g'(n)

f_{2}(n) <= c_{2}g_{2}(n) <= c_{2}g'(n)

f_{1}(n) + f_{2}(n) <= c_{1}g'(n) + c_{2}g'(n) = c'g'(n)

Therefore, f_{1}(n) + f_{2}(n) is O(g'(n)) = O(max(g_{1}(n),g_{2}(n)))

Similar Questions

I'm interesting in rewrite rule to modify some url and paths. Here some Examples. I have some hostnames which lookups to 1 VirtualHost throught ServerAlias in Apache conf. example.com anotherdomain.c

As I understand it there are two steps to proving that a problem is NP complete: Give an algorithm that can verify a solution to the problem in polynomial time. That is, an algorithm whose input is a

I have created a this rule: <rewrite> <rules> <rule name=ImageRedirect stopProcessing=false> <match url=^(.*)/(.*)/ /> <action type=Rewrite url=http://www.lrgimages

I need to read the condition of a shopping cart price rule in magento programatically. Mage_SalesRule_Model_Rule has a method getConditionsSerialized() which does provide the conditions but in a cryp

SELECT x,y,SUM(f)-SUM(g) FROM a,b WHERE a.x = b.x GROUP BY SUM(f)-SUM(g) HAVING SUM(f)-SUM(g)>1 When trying with GROUP BY x, it works but how can I GROUP BY SUM(f)-SUM(g) ??

in Yii framework, can I use unique validation rule to check uniqueness of an field within some condition (I know there is criteria, but this condition is a bit tricky)? Ie, i want to check num_days un

SELECT f.nummer AS factuur_id, f.mvoor AS factuur, f.faktuurnr AS factuur_nr, f.topdatum AS factuur_datum, f.vervaldag AS factuur_vervaldatum, f.totbruto AS factuur_totaal, SUM(c.totbruto) AS credit_t

I need help proving the following: (a ∨ b) ∨ c = a ∨ (b ∨ c) I don't want the answer... just a hint that will help me understand the process of proving this. Thank you.

what is the linq query from this sql query SELECT sum(IIF(jenis = 'primer',1,0)) as sum_primer, sum(IIF(jenis = 'sekunder',1,0)) as sum_sekunder FROM cooperations Try to search same example from 101

I am completely unfamiliar with .htaccess and have been looking through forums and trying several examples to try and construct a htaccess rule that will solve our problem. We have had a rule in place

I've read that The Rule of Three, What is The Rule of Three? is summarized as follows: If you need to explicitly declare either the destructor, copy constructor or copy assignment operator yourself,

I have the next rules % Signature: natural_number(N)/1 % Purpose: N is a natural number. natural_number(0). natural_number(s(X)) :- natural_number(X) ackermann(0, N, s(N)). //rule 1 ackermann(s(M),0,R

We're trying to implement a rule on certain mailboxes that it shouldn't accept an email without a subject. I found documentation from Microsoft on exchange 2010 to Configure a Transport Rule for Messa

I understand the concept of big theta, big oh, and big omega.. I'm just having a hard time proving it. It's been a long time since I've done induction, so I'm pretty sure I'm just rusty and missing so

3.8. Optional Sequence: [RULE] Square brackets enclose an optional element sequence: [foo bar] is equivalent to *1(foo bar). The above section from RFC5234 seems not correct to me. I think this is be

I was wondering if there is a way to define hierarchy (not just order of execution) between rules and control the rule execution - i.e. if the parent rule fired then the ones below should not be evalu

I am trying to apply the folowing css rule div#ja-navhelper.wrap { display: none !important; } to the following joomla site http://nuevas-tecnologias.org/index.php but it is not working any idea why?

i have file page1.html, i want rename it to page1.php but it must be accessible to old name pag1.html what rule in htaccess i must write?

I have to use multiple recurrence rules and exception rules in icalendar file, as I have read in specification (RFC 2445) that multiple instances of recurrence rule and exception rule can be specified

How do I represent a direct descendent CSS rule in SASS? Ex. body > div { ... } Couldn't seem to find it in the docs: http://sass-lang.com/docs/yardoc/file.SASS_REFERENCE.html

I am trying to test whenDescriptor rule in following grammar in AntLRWorks. I keep getting following exception as soon as I start debugging. Input text for testing is when order : OrderBll then [1

I have this rule in my iptables: sudo iptables -t nat -nvL --line-numbers Chain PREROUTING (policy ACCEPT 14 packets, 1950 bytes) num pkts bytes target prot opt in out source destination Chain INPUT (

public float sum(Object ob) { float sum = 0; for (int i = 0; i < ob.length; i++) { sum += ob[i]; } return sum; } How can I implement a function that would return the sum of all the array elements

This is a simplified version of how to dynamically change a selector rule: http://jsfiddle.net/vsync/SaQy6/ For a giver inline style: <style type='text/css' id='myStyle'> ul > li{} </style

I am inserting data to drools rule engine but i can not understand how it processed inserted data. The code for inserting data is: final StatefulKnowledgeSession session = getSession() new Thread() {

Is it possible for a Bison rule to expand instead of reducing so that it turns into more tokens? Asked a different way: is it possible to insert extra tokens to be parsed before the next token in the

I have managed to put this condition and rule below together to redirect a page to include index.shtml at the end of it but I dont understand what this part of the Rewrite means - the ^$ part. I belie

I want to erase and clean my code a bit. I have this rule in .htaccess RewriteRule ^(.+),(.+),(.+),([0-9]+).php$ /hotels/description/$4/3 RewriteRule ^(.+)+(.+)-([0-9]+).php$ /hotels/description/$3/

I am having some difficulty in understanding how a String[] can be represented in a Guvnor rule. How can an array of strings be passed to a Java method that uses String[] as an argument from a rule in

I have a questions Regarding PHP Basic Coding Standards PSR1. PSR 1 Rule 2.3 states ##Rule 2.3 Side Effects## A file SHOULD declare new symbols (classes, functions, constants, etc.) and cause no other

I have URL rewrite rule: RewriteCond %{REQUEST_FILENAME} !-f RewriteCond %{REQUEST_FILENAME} !-d RewriteCond %{REQUEST_URI} !^/sites/ RewriteRule ^([^/]+)/?(.*)$ sites/$1/$2 [NC,L] When this URL is c

jsFiddle I have a vertical rule within a div (actually the border-right of a nested div). However, I am having trouble making it span the whole of its container. I have tried modifying the margins (

Is there any way to integrate Rule Engine (or Rule Engine concept to apply Business Rules) with AngularJS application? I have heard about Drools. Is there any API provided by Drools which can be used

I was trying to write a fortify rule which just checks for a function and flags it when the function comes up. I created a java file with the following code: class t { public static void main(String[]

please help a newbie to understand this warning in ANTLWorks: [11:10:15] warning(138): BooleanExpr.g:0:1: grammar BooleanExpr: no start rule (no rule can obviously be followed by EOF) This is how de

I am trying to use the Kohana Validation Factory in this way: $post = validation::factory($_POST) ->rule('payorid', 'not_empty') ->rule('payortype', 'not_empty') ->rule('individual_first_name

I am trying to create a prolog rule which will generate all the people in a social network using S number degrees of separation. This is the rule that i have made but it is only printing empty lists.

I'm trying to code a context-sensitive lexer rule using ANTLR but can't get it to do what I need. The rule needs to match 1 of 2 alternatives based on characters found in the beginning of the rule. Be

I'm trying to do a sum on a group with a total of the sum at the end of the report. Basically in the group header field I need to sum 5 fields to create a total. This is easy with a simple formula th

On my CodeIgniter site, I would like to add a specific rewrite rule, so that this url http://www.exemple.com/cache.manifest would rewrite to http://www.exemple.com/controller/manifest (because Safari

I don't understand why is this rule not working? If I change total quantity equals or greater than from 1 (visible as TRUE) to 0 (visible as FALSE), the rule applies to every single product in the s

I want to get the sum of values of the rows with field_id 31 33 35 37 39 41. This is the print screen from the table I use this code to get the sum of all values of one field SELECT field_id, SUM(val

I'm having difficulty proving that the 'bad' version of fibonacci is O(2^n). Ie. Given the function int fib(int x) { if ( x == 1 || x == 2 ) { return 1; } else { return ( f( x - 1 ) + f( x - 2) ); } }

I'm trying to figure out a regex for this rule: Must contain minimum 3 and maximum 5 numeric chars. The same character can be repeated max. 5 times! Also, the length should be minim 10 chars. Do y

I have a min height rule on the bottom of this page for an element I can't find the rule to edit to save my life. I just need to reduce the space on the bottom of the site. Users have been very helpfu

This question already has an answer here: How to sum array of numbers in Ruby? 12 answers Q: Write a method, sum which takes an array of numbers and returns the sum of the numbers. A: def sum(n

in yacc/bison grammars, is there a way from within a mid-rule action to discard the rule altogether, but without an error (and the call to yyerror), so that other options would still be valid (similar

How do i use rewrite rule with 3 parameteres? like: RewriteRule example/$/$/$ example.php?x=$1&y=$2&z=$3 thank you

Is it possible to use MySql SUM() function inside another MySql SUM() function ?? Like below $query=SELECT SUM(Table1.Column1+SUM(Table2.Column2+Table2.Column3)) from Table1 LEFT JOIN Table2 ON Table

DBLint is used to check database status. There are 46 rules. At www.dblint.org there are some simple explainations of each rule, but the Rule 31 which is described as below: Defined Primary Key is not