dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Testing Time Complexity

  1. #1
    Join Date
    May 2004
    Posts
    249

    Testing Time Complexity

    Well this is my homework question. But it is not graded

    I am to find the time complexity of the below

    Name:  Capture.JPG
Views: 127
Size:  12.0 KB

    So i came up wtih the following:

    Code:
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
    
    	int k = 1;
    	int n = 0;
    
    	cout << "please enter n: ";
    	cin >> n;
    	cout << endl << endl;
    
    	for (int i = 0; i < n; i++)
    	{
    		k = k * 2;
    		for (int j = 0; j < k; j++)
    			cout << /*"j = " << j << "\t"*/ endl;
    		cout << "k = " << k << "\t";
    	}
    
    	return 0;
    }
    The results are as follows

    Name:  Capture1.JPG
Views: 113
Size:  19.4 KB

    My question is, what is the figure/number that would go into the third column?

    I found out that k = 2^n
    but i need to find out T(n)
    --------------------------------------------------
    Please pardon me for having bad English.

  2. #2
    Join Date
    May 2004
    Posts
    249

    Re: Testing Time Complexity

    I will formulate my own equation. I just need a few figures to get going
    --------------------------------------------------
    Please pardon me for having bad English.

  3. #3
    Join Date
    Jun 2015
    Posts
    208

    Re: Testing Time Complexity

    Quote Originally Posted by rockx View Post
    I found out that k = 2^n
    but i need to find out T(n)
    Well if T(n) is the actual number of iterations then you should sum up all k's from 0 to n. You get,

    T(n) = 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^n = 2^(n+1) - 1

  4. #4
    Join Date
    May 2004
    Posts
    249

    Re: Testing Time Complexity

    thanks T
    --------------------------------------------------
    Please pardon me for having bad English.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)