algorithm - 漸化式：証明（n / 2）+（n / 2）= O（n）

Question

だから私はこのようなアルゴリズムを持っているとしましょう：

void dummy_algorithm(int a[]) {
   int center = floor(a.length/2);
   //For reference purposes: Loop 1  
   for(int i = 0; i < center; i++) {
       //The best code you've ever seen
   }
   //Loop 2
   for(int j = center + 1; j < a.length; j++) {
      //Slightly less awesome code
   }
}

それはかなり基本的なものです。私は両方のループが配列の半分を反復することを知っているので、それぞれに（n / 2）の複雑さが与えられます。ただし、このメソッドが実行する作業の合計は明らかにO（n）です。

したがって、私の質問は、このアルゴリズムがO（n）であることを（漸化式を介して）どのように証明するのですか？それとも私はこれについて完全に間違っていますか？

注：2つのループを1つに結合することはできません。それらは、最終的に再帰呼び出しに入るアクションを実行します。あなたが考えることができる他のものは許可されていません。この問題には多くの制約があります。

Answer 1

O(x) + O(y) = O(x+y)の証明を本当に探している場合は、次の行に沿って機能します。

R1 ∈ O(x) ∧ R2 ∈ O(y)
⇒ ∃ a. R1 < ax ∧ ∃ b. R2 < by
⇒ ∃ a, b. R1 < ax ∧ R2 < by
⇒ ∃ a, b. R1+R2 < ax + by
⇒ ∃ a, b. c=max(a,b) ∧ R1+R2 < cx + cy
⇒ ∃ c. R1+R2 < c(x+y)
⇒ R1+R2 ∈ O(x+y)

Answer 2

  (N/2) + (N/2)
= 2*(N/2)
= 2N/2
= N