-3

Say theres a recursive function which runs n times and a nested for loop that runs n^2 times, what will be its time complexity O(n) or O(n^3)

For example :

fun(int n) {
if(n==1) return;

for(i=0;i<n;i++) 
  for(j=0;j<n;j++) 
    printf("A");

}
S.S. Anne
  • 15,171
  • 8
  • 38
  • 76
Anmol Majithia
  • 21
  • 2
  • Well, what's `n*n^2`? – 3ch0 Oct 03 '19 at 13:48
  • Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – S.S. Anne Oct 03 '19 at 13:49
  • Something is really wrong with this edit. OP describes a recursive function yet the edit removes recursion! OP, please go back and fix your question to make the code how you mean it to be. – Gabriel Staples Oct 03 '19 at 14:13

1 Answers1

-2

the time complexity of the above function is O(n^3).

look as it as for every n, the loops s will run n(n+1)/2 times and this will take place n time. So the total number of iterations will be (n^2)(n+1)/2 which is O(n^3).

Aditya Gaddhyan
  • 354
  • 1
  • 14