このコードのBig-Oとは何ですか？

Question

最近、私はこの質問があったという試験を受けました：gの時間複雑さは何ですか？

int f(int *arr, int n, int m) 
{ 
    if(n == 0) 
    { 
     if(m == 0) 
      return 3; 

     return arr[m] + f(arr, n, m - 1); 
    } 

    return f(arr, n - 1, m); 
} 

int g(int *arr, int n) 
{ 
    return f(arr, n, n); 
} 

は今、2 *は明らかに存在しているとして、私と私の友人のほとんどは、O（n）を答えN F個と他には何のために呼び出しますが、教授の答えはO（N^2）でした。 誰かが私に正しい人を説明することはできますか？それが彼なら、理由を説明できますか？

Answer 1

EDIT：ポストで

、私は私が間違っている問題を解決したことを実現します。私は内部関数呼び出しがf(arr, m, m - 1)のときに解決していました。その場合、時間の複雑さは確かにO（n²）です。質問の投稿方法は、時間の複雑さはO（n）です。しかし、私はこのポストを去ります。なぜならこれは教授が誤解した可能性が高いからです。したがって、以下の回答は、試験の質問が参考になる可能性が高い方法で書かれています。 n == 0 nはスタックに呼び出すことを意味し、f() n回再帰的に

1. コール：

   が取られるステップを考えてみましょう。

2. 今、この最低限の関数呼び出しでは、if文を入力できます。
3. もう一度f()と呼んでmを減らしますが、mを第2引数として呼び出して元のn値を維持します。
4. この新しい「再帰的な」スタックでは、最初にf()をn（またはm）回呼び出してからmを1減らす必要があります。
5. m == 0に戻ると、返品できます。

このグラフを見ると、すべての「単位」はf()への1回の呼び出しを表します。 n == 0の場合、3番目の引数をもう一度呼び出し、mを1減らしてレベルを下げます。

このグラフ中の矩形の面積がn * mとm == nあるので、それはf()がn²回呼び出され、コードはO（n²）時間複雑性を有していることを意味します。