与えられたコードの複雑さを見つける

Question

私は与えられたコードの複雑さを見つけるために戦っています。私は、正確な複雑さを特定し、複雑さを実際にどのように分析するのか苦労していると思います。

public void doThings(int[] arr, int start){ 
    boolean found = false; 
    int i = start; 
    while ((found != true) && (i<arr.length)){ 
     i++; 
     if (arr[i]==17){ 
      found=true; 
     } 
    } 
} 
public void reorganize(int[] arr){ 
    for (int i=0; i<arr.length; i++){ 
     doThings(arr, i); 
    } 
} 

質問は以下のとおりです：次のように分析するためのコードがある

1）の再編成方法の、それがどのような入力を発生しないための最良のケースの複雑さは何ですか？
2）再編成方法の最悪の複雑さはどのような入力ですか？

私の答えは以下のとおりです。

1）再編成方法について発生する可能性がある2の可能な最良の例があります。 1つは、配列の長さが1のときです。つまり、reorganizeメソッドとdoThingsメソッドのループが1回だけ実行されることを意味します。もう1つの可能性は、配列のi番目の項目が17であることを意味します。つまり、doThingsループはそのi番目の繰り返しで完全には実行されません。したがって、両方の場合において、最良の場合=Ο（n）である。

2）最悪の場合は、番号17が配列の最後にあり、番号17が配列にない場合です。これは、配列がn×n回横断され、最悪の場合がΟ（n^2）であることを意味します。

私の質問が正しく答える手助けをしてください。私の質問が間違っていて、可能であれば問題を説明してください。

Answer 1

"ベストケース"の配列が空で、何も検索しません。

最悪の場合は、17個を見ることができないため、すべての要素を見ていることです。それ以外の場合はすべて間にあります。

if (arr[i]==17){はコードの「最もホットなパス」であり、最も頻繁に実行されることを意味します。

あなたがfound = trueを設定した場合でも、reorganize方法は、それについて知らない終わっていない、と続けるので、それは常に最悪の場合にはn*(n-1)/2回（私はその権利数学をしたと思う）の合計を実行しますすでにアレイ全体をスキャンしていても検索することができます。

基本的に、メソッドなしでコードを平坦化します。あなたはこの質問をしています。

What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?