-3

So my doubt is at line 2, here can we suppose that array2 is nested in array1, what would be the time complexity there from O(n^2) or O(n) why? 

function1()
{
  for-loop1{ function2(); } //line 2
}

function2()
{
  for-loop2(); 
}
Vivek Rajaurya
  • 1
  • 1
  • Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – achAmháin Apr 25 '18 at 12:59
  • 1
    We need to see what these functions are doing. – Tim Biegeleisen Apr 25 '18 at 13:00
  • Ofcourse it'll be included. – Shanu Gupta Apr 25 '18 at 13:00
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [On topic](http://stackoverflow.com/help/on-topic) and [how to ask](http://stackoverflow.com/help/how-to-ask) apply here. StackOverflow is not a design, coding, research, or tutorial service. – Prune Apr 25 '18 at 17:51
  • Your posted code has a complexity of **O(1)**: it fails in constant time because of the semantic errors. `array1` and `array2` are undefined. – Prune Apr 25 '18 at 17:53

1 Answers1

0

The Big O notation of your example is hard to decide since it does not run any actual function. You have to understand that Big O describes how the number of executions/calculations done relates to the input size.

  • If the function you provided does a fixed number of operations for every element in array1 and a fixed number for those in array2 then the case is O(n).
  • If it loop through the array again for each element in the array, then it's O(n^2) since doubling the size would lead to 4 times the amount of computation.
Jotunacorn
  • 496
  • 1
  • 4
  • 12