Running Time Calculation

user_17005197 0
Viewed 60

I am trying to learn time complexities. I have come across a problem that is confusing me. I need help to understand this:

my_func takes an array input of size n. It runs three for loops. In the third loop it calls for another function that is O(1) time.

def my_func(A): 
  for (int i=1; i<n; i++)
    for (int j=1; j<i; j++)
      for (int k=1; k<j; k++)
        some_other_func();

My Questions:

  1. Am I right if I say that total number of steps performed by my_func() is O(n^3) because:
    1. the first for loop goes from 1 to n-1
    2. the second for loop goes from 1 to n-2
    3. the third loop goes from 1 to n-3
  2. What is asymptotic run time and what is the asymptotic run time for the above algorithm?
  3. What is the meaning of the following:

enter image description here

code-complexity complexity-theory time-complexity
2 Answers

Am I right if I say that total number of steps performed by my_func() is O(n^3)

Yes, its time-complexity is O(n^3).

What is asymptotic run time and what is the asymptotic run time for the above algorithm?

The limiting behavior of the execution time of an algorithm when the size of the problem goes to infinity [here]. for example:

lim (n^3) when n-> infinite

What is the meaning of the following

1st, it shows dependant variables k->j->i as it is. Moreover, what if all of the variables(i, j, k) were independent of each other? for example a constant x then each loop would iterate for x times but here k depends on j, and j depends on I. for example:

x(x(x)) = sigma(sigma(sigma(O(1))))

2nd, time-complexity is investigated on large input. Therefore, either the variables are dependant or non-dependant, big O would be O(n^3).

user_60717290

Yes, it's O(n^3), and that IS the asymptotic run time. The sum expression at the end means the same thing as the three nested loops at the top, assuming "some_other_func()" is sum = sum + 1.

user_18833160
Related