The Gateway to Computer Science Excellence

+6 votes

Best answer

The below part introduces (n*m) time complexity

```
for I = 1 to N do // *n times
if ((not FINISH[i]) and
NEEDi <= WORK) then // *m times, if it's an array search
```

but it is also nested in a *repeat* loop. If that loop can run, in worst case, n times, then the procedure has O(n*n*m) time complexity.

```
WORK = WORK + ALLOCATION_i; // also O(m) operation, vectors addition
```

So, the code that executes in the *for* loop has O(m+m) time complexity.

Of course, O(m+m) = O(m) and the *final* complexity is O(n*n*m).

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,479 answers

195,421 comments

100,558 users