Determining the time complexity of this code?

Question

I think the time complexity of this code will be O(n^2) but I am not sure so if someone can explain what will be the time complexity of this code it would be really helpful

int func2()
{
    int i, j, k = 0;
    scanf("%d", &n);
    for (i = 1; i < n; i++)
    {
        i -= 1;
        i *= 2;
        k = k + i;
        for (j = 1; j < n; j++);
    }
}

There's a lot wrong with the code, which makes it really hard to answer your question. In general, the asymptotic complexity is also language-agnostic, so using a description of the algorithm in pseudocode would be a better approach than the flawed C code. As a new user here, please also take the [tour] and read [ask]. — Ulrich Eckhardt, Aug 22 '21 at 08:38
uh well i got this question in my quiz yesterday and i was super confused due to the code and i had said this before but looks like all the comments disappeared for some reason and i have a REALLY bad teacher so you can understand why this is a super flawed c code. — Adam, Aug 22 '21 at 08:44
If you are confused by the code, you could ask a question something like "In a quiz yesterday, I got asked the complexity of this code, but I can't understand (list of things you can't understand). What are the ways in which this code is wrong, and in what ways is my understanding wrong". You've asked a different question to what your actual problem is, and so not got the most helpful responses. (Note that such a question and the answers it produces can be used to give excellent feedback to your teacher about his quiz question). — Paul Hankin, Aug 22 '21 at 08:52

score 2 · Answer 1 · answered Aug 22 '21 at 07:30

It looks like an infinite loop to me, so the time complexity is O(infinity).

On the first iteration of the outer loop, i -= 1 will set i to 0. Multiplying by 2 leaves it still 0.

The loop iteration i++ will then increment i to 1, and the next iteration will repeat the above computations.

score 1 · Answer 2 · answered Aug 22 '21 at 08:17

I am a beginner on time complexity but these are my views:- The outer for loop is in the condition of an infinite loop as on the first iteration of the outer loop, execution starts with i=1. On executing i -= 1 it will set i=0. Executing i*=2, the value of i remains the same as 0. On going in the increment phase, i is incremented and i=1. So the same process occurs. Thus the value of i remains the same causing it to run indefinitely. Now, coming forward inside the outer for loop is a nested for (in the variable j) loop that is followed by a semicolon. This causes it to have a time complexity of O(1). So the resultant overall time complexity can be expected to be O(infinity).

I don't understand the point made on the _semicolon_. This is C code. — Brandt, Aug 23 '21 at 07:01
The semicolon stands for an empty loop body(https://stackoverflow.com/questions/13421395/effect-of-semicolon-after-for-loop) so besides counting, that loop does not do anything. — Richard, Aug 23 '21 at 14:42

score 0 · Answer 3 · answered Aug 22 '21 at 08:20

0

First, 'n' not declared here and input value is being assigned to it.

Second, technically, this code is an infinite loop (done ridiculously hard way) and for non-terminating, forever-running algorithms the time-complexity is 'Undefined' as by the principles of Algorithm Analysis, time-complexity is only computed for algorithms that perform a task with certainity to terminate.

In case if this would have been a terminating loop, time complexity of this function is O(n^2) would have been quadratic in nature due to nesting of for(;;) inside of another for(;;) with enclosed statements of O(1) - linear time complexity. The higher order complexity ( O(n^2) ) supersedes.

answered Aug 22 '21 at 08:20

Emaad Hassan

41
4

If the code terminates (for example if the for loop started from i=2 rather than i=1), the runtime would be Theta(n log n), because i approximately doubles each iteration. Nested for loops don't mean O(n^2), except in simple cases and it's a common mistake to use this "rule". – Paul Hankin Aug 22 '21 at 08:35
Yes ! that is a correcct understanding. The rules of time complexity don't apply on ditto-basis. You have to interpret what code is actually doing. Like in the case here, it is implementing an infinite loop by twisting the code, which otherwise, could have been done by a simple while(1). – Emaad Hassan Aug 22 '21 at 08:51

Determining the time complexity of this code?

3 Answers3