• edited by
931 views
1 1 vote

Consider the following program:

for(i=0;i<=n;i++) 
    for(i=0;i<=n;i++) 
        for(i=0;i<=n;i++)
            print(GO);


What is TC for above program??

2 Answers

Best answer
8 8 votes
for(i=0;i<=n;i++) //outer
    for(i=0;i<=n;i++) //inner
        for(i=0;i<=n;i++)//innermost-loop
            print(GO);

Initially $i= 0$ for outer loop. then, inner loop gets executed and then innermost loop executes setting $i=0$ and executes for $n+1$ times as $i= 0$ to $i = n$, At the end when $i = n+1$ Innermost loop executes to be false. then $i++$ makes $i = n+2$ and condition for inner loop executes to be false and then for outer loop condition is checked after checking condition which evalutes to be false. So, GO is printed $n+1$ times as $i = 0$ to $i=n+1$.

So, TC $=\color{blue}{\theta(n)}$. A further interesting question would be what is the final value of $i$.

• selected by
4 4 votes
it seems to be O(n).. because the same variable is used in all three loops.. so only one time initialization is performed.. and further i is incremented till i<n..
Position:
Show:

Related questions

3 3 votes
1 1 answer
211
211 views
GO Classes asked Aug 31
211 views
The algorithm $\text{ALGSORT}$ sorts an array of distinct integers using comparisons.The function $\text{MININDEX(V,i,j)}$ returns the position of the smallest element in...
1 1 vote
1 1 answer
146
146 views
GO Classes asked Aug 29
146 views
Suppose Huffman coding is implemented as follows.Initially, the $n$ symbols are stored in a min priority queue according to their frequencies.The algorithm repeatedly per...
1 1 vote
1 1 answer
125
125 views
GO Classes asked Aug 26
125 views
Consider,f1(N): x = 0 for i = 0 to N - 1: x++ return xand,f2(N, R): x = 0 for i = 0 to N - 1: for j = 1; j <= R; j = j + j: x = x + f1(j) return xWhat is the order of gro...
0 0 votes
0 0 answers
313
313 views
Vennapusa_Gurunath_r asked Dec 12, 2024
313 views
Please give me suggestion I am Good at conceptual in algorithms but i am issue facing at Find time complexity of any problem.What Can i do resolve this problem .I revised...