Register

GO Classes DPP | GATE CS | Algorithms | Code Complexity

132 views

1 Answer

0 0 votes

The outer loop runs $n$ times.

For every value of $i$, the middle loop also runs $n$ times.

For every pair $(i, j)$, the inner loop runs $n$ times.

So the total number of executions of the innermost statement is:

$n \times n \times n = n^3$

The statement:

$\texttt{total += i * j * k}$

takes constant time.

Therefore, total time complexity is: $O(n^3)$

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

4 4 votes
1 1 answer
128
128 views
GO Classes asked Jul 29
128 views
GO Classes DPP | GATE CS | Algorithms | Code Complexity
Consider the following recursive C function:int fun(int n) { if (n <= 1) { return n; } else { return fun(n - 1) + fun(n - 2); } }What is the time complexity of $\texttt{f...
2 2 votes
1 1 answer
114
114 views
GO Classes asked Jul 29
114 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Growth
Suppose $f(n) \in \Omega(n^2)$.Classify the following statements:$\text{S1}$. $f(n) \in \Omega(n^3)$ $\text{S2}$. $f(n) \in \Omega(n)$ $\text{S3}$. $f(n) \in O(n)$ $\text...
3 3 votes
1 1 answer
121
121 views
GO Classes asked Jul 29
121 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Growth
Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = n^{\sqrt n}$$f_2(n) = 2^n$$f_3(n) = n^{10}\cdot 2^{n/2}$$f_4(n) = \sum_{i=1}^{n}(i+1)$ ...
2 2 votes
1 1 answer
109
109 views
GO Classes asked Jul 29
109 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Growth
Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = 2^{2^{1000000}}$$f_2(n) = 2^{100000n}$$f_3(n) = {}^{n}C_{2}$$f_4(n) = n\sqrt n$ $f_1(n)...