-1

I am new at run time complexity. I have run across this code. I am confused on what the runtime complexity of this is...

    for (i = 1; i < n; i++)
    {
        for (j = 1; j <= n; j = div(j))
        {
            printf("Algorithm is fun");
        }
        printf("\n");
    }

Is it O(n^2) or Nlogn ? Any anyone explain ?

MrRedRrebbitXYZ
  • 1
  • 3
  • 1
    What does div do? – cipher94 Jul 21 '20 at 09:24
  • First, this isn't a complete question since it's not possible to answer unless `div` is given. Second, what have you done to find the complexity already? Depending on what `div` is, there's probably already duplicates of the question here, and https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it answers the general problem of calculating complexity. – Paul Hankin Jul 21 '20 at 10:06
  • https://www.geeksforgeeks.org/div-function-c/ i think this – MrRedRrebbitXYZ Jul 21 '20 at 10:10
  • If you don't know what `div` is and have to guess, how can the question be answerable? Probably you need to ask whoever set you this question. If you want an answer, can you make a complete and minimal program? Note that the `div` you link to has 2 arguments, but the one in your code takes one. – Paul Hankin Jul 21 '20 at 10:13
  • with one argument, the div function makes the value of j 0 and it continues like this, the loop runs............. from observation https://ideone.com/dxl3no – MrRedRrebbitXYZ Jul 21 '20 at 10:44
  • The behavior is undefined if you use a 2-argument function with only 1 argument. That means your program could literally do anything. Presumably you got a warning when you compiled it? – Paul Hankin Jul 21 '20 at 12:50
  • Note that `div` from the stdlib returns `div_t` which is a struct type, so assigning the return value to an int is also very wrong. – Paul Hankin Jul 21 '20 at 12:53

2 Answers2

0

It will depend upon the functionality of div(j). If it increases/decreases j by 2, time complexity will be O(logn).

Because the inner loop will run at most log(n) times for every i.

for (int i = 1; i < n; i++)
{
    for (int j = 1; j <= n; j = div(j))
    {
        cout<<"Algorithm is fun"; // almost logn times , j = 1, 2, 4...till it reaches n.
    }
    cout<< endl;
}
int div(j) {
 return j = j*2)
}
cipher94
  • 203
  • 1
  • 12
  • div is already a function that divides integers, why did you declare your own definition for it? – maha Jul 21 '20 at 09:31
  • I was not sure what div does, to give you an idea I created one. If you can tell me what div will return if you pass j to it, it will be helpful to explain it more. divides integers -> this is not clear. – cipher94 Jul 21 '20 at 09:33
  • if i knew exactly i would've answered the question lol, it should take 2 parameters and divide them, the code from the question doesn't even compile for me because it's asking for a second parameter.. check this link https://www.geeksforgeeks.org/div-function-c/ – maha Jul 21 '20 at 09:35
  • The question which you have asked you should have written what it does in the first place. Now coming to what div returns it returns a struct of quotient and remainder, you have to select one of those according to your use case, and it take 2 parameters. SO is meant for clear doubts, not with ambiguity. – cipher94 Jul 21 '20 at 09:37
  • i didn't know at the time and was confused of why you created your own method.. i started searching after and you should've done that too – maha Jul 21 '20 at 09:39
  • Your goal was to be helpful, but it's better to leave a question unanswered or to ask for clarification if it's ambiguous. You've guessed that `div` multiplies `j` by 2 which is possible, but doesn't even seem that likely given the name. That said, it's hard to think of any reasonable definition of `div` that matches the name and where the algorithm terminates. – Paul Hankin Jul 21 '20 at 10:09
0

When you have a for loop, its total runtime is the sum of the runtimes of each individual iteration.

If all iterations have the same runtime, then the total runtime of the for loop is the number of iterations multiplied by the runtime of each iteration.

For instance if I write the code:

for (int i = 0; i < 10000; ++i)
{
    std::cout << "Hello " << i << std::endl;
}

Then 10000 lines will be written to output, and you can say this is the runtime of your algorithm.

But if I write the code:

for (int i = 0; i < 10000; ++i)
{
    some_complex_and_slow_function();
}

Then some_complex_and_slow_function() will be called 10000 times, therefore the total runtime will be 10000 times the runtime of some_complex_and_slow_function().

In your case, you have a for loop with another for loop inside. So you need to find out: what is the runtime of the inner for loop (which is the same as asking how many iterations it has), and what is the number of iterations of the outer loop.

Please try to answer these two questions, and ask again if you still have doubts.

Stef
  • 13,242
  • 2
  • 17
  • 28
  • for the outer loop i think it should be O(n), for the inner loop it seems there is a function called div, but as there is no denominator given it will always return 1, so the inner loop will never end hence will result in infinity or TLE. Or that is what i think now. ref, https://www.geeksforgeeks.org/div-function-c/ – MrRedRrebbitXYZ Jul 21 '20 at 10:13
  • Yes, you need to figure out what this div function does. Otherwise your question cannot be answered. cipher94 gave a good answer assuming `div(j)` is equivalent to `j*2`, which would explain the possible n log(n) complexity you mentioned in your question. But it's weird calling this function `div` if what it does is multiply by 2. The link you gave requires `div` to have two arguments, but it only has one argument in your code. So it cannot be the same function. Please find out what `div` was in your context. – Stef Jul 21 '20 at 10:18
  • this exact code runs forver in c for valid value of n. so i guess the complexity is infinity. bit confused about the div function though – MrRedRrebbitXYZ Jul 21 '20 at 10:26
  • "this exact code" doesn't have a `main()` function, so it's not a valid C program. can you please post your full C program that runs forever? – Stef Jul 21 '20 at 10:30
  • ```#include int main() { int i, j, n = 5; for (i = 1; i < n; i++) { for (j = 1; j <= n; j = div(j)) { printf("Algorithm is fun"); } printf("\n"); } return 0; } ``` – MrRedRrebbitXYZ Jul 21 '20 at 10:35
  • so, i after observing and testing it, it seems div(j) makes the value 0 and the loops runs.......... – MrRedRrebbitXYZ Jul 21 '20 at 10:42
  • Your code doesn't compile without a warning because `div` is defined in `stdlib.h` and you haven't included that. If you include that header, the code doesn't compile at all (because of the mismatched types). – Paul Hankin Jul 21 '20 at 12:55