Analyze these functions. For each function, give the complete T(n)(or T(m,n), or

Question

Analyze these functions. For each function, give the complete T(n)(or T(m,n), or whatever is appropriate), then find the tightesttime complexity you can, in big-Oh notation. You need not showevery step in getting from T(n) to big-Oh. You should assume allinputs are > 0.

1.  int f1(int n) {
       int i = 1;                      // c1
       for (int j = 1;                 // c2
       j <= n;         // c3
       j++) {  // c4
       i = i * j;                  // c5
       }
       return i;                       // c6
       }
   

2.  int f2(int m, unsigned int n) {
       for (int i = 0;                    // c1
       i < 2 * m;         // c2
       i++) {  // c3
       for (int j = n;                // c4
       j > 0;         // c5
       j--) {  // c6
       return j;                  // c7
       }
       }
       return 0;                          // c8
       }
   

3.  void f3(int n) {
       for (int i = 0;                        // c1
       i < n;                 // c2
       i++) {          // c3
       for (int j = 10;                   // c4
       j >= 0;           // c5
       j--) {    // c6
       cout << "i = " << i;           // c7
       cout << ", j = " << j << endl; // c8
       }
       }
       }
   

Explanation / Answer

This loop will run11n times,
so order will be O(n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---