For each of the following loops with a method call determine

For each of the following loops with a method call, determine the overall time complexity. Assume that method foo() takes constant time, and that method faa() takes time linear in the value of its parameter.

for (j = 0; j < n; j++)

foo(j);

for (j = 0; j < n; j++)

faa(j);

for j =0; j < n; j++)

faa(k);

also if you could explain how this is done it would be grealy apreciated.

Solution

Since method foo takes constant time, so foo will be called n times so the the time taken by foo in n times will be n*1 which is n. So the Time complexity of this loop will be O(n) time.

Since faa(j) is taking linear time based on it\'s value so here the loop is running n times so the value faa(j) will be called n times and since faa(j) is taking linear time then we can say the time taken by this code snippet will be n*n which is n² So the Time complexity will be O(n²).

faa(k) is called n times but it\'s parameter is not changing since faa(k) with the same value is called n times so here the time complexity will be of O(n).