algorithm - What is the total running time of the following code (N is an int variable) -

i preparing exam, came question:

what total running time of following code (n int variable)

z z = new z(n); (int = 0; < n; i++) z.insert("bob", i); 

class z:

public class z {      string[] names;      integer[] numbers;      int n = 0;       public z(int cap)      {         names = new string[cap];         numbers = new integer[cap];      }        public integer find(string s)      {         (int = 0; < n; i++)         {             if (names[i].equals(s)) return numbers[i];         }         return null;      }      public void insert(string s, integer m)     {         (int = 0; < n; i++)         {             if (names[i].equals(s)) numbers[i] = m;         }         names[n] = s;         numbers[n] = m;         n++;     } } 

i think answer question o(n^2). first loop takes o(n) times, , method insert takes o(n) times (notice: n++ on every insert call), total gives o(n^2)

first note n variable in main part not same n referenced within object instance.

after z object created, private n member equal 0 , increases every call insert.

so number of times loop in insert method iterates equal number of previous calls made insert method.

so total number iterations made in insert method (taking n calls together) is:

 Σ_i=0..n-1 (i)

this equal to:

 ½n(n-1)

which ½n² - ½n , o(n²)