Complexity Analysis

Jokky · #1 22-Jun-2006, 10:25

I'm starting to learn about Complexity Analysis and am finding my text a little hard to understand. I borrowed a book from someone to learn it and in the book it has a problem that asks:

Find the complexity of the function used to find the kth smallest integer in an unordered list array of integers.

CPP / C++ / C Code:

int selectkth(int a[], int k, int n)  {
	int i, j, mini, tmp;
	for (i = 0; i < k; i++) {
		mini = i;
		for (j = i+1; j < n; j++) 
			if (a[j]<a[mini])
				mini = j;
		tmp = a[i];
		a[i] = a[mini];
		a[mini] = tmp;
	}
	return a[k-1];

Blake · #2 22-Jun-2006, 20:13

It's O(nk). That's not a tight bound though.

Jokky · #3 23-Jun-2006, 13:05

Quote:

Originally Posted by Blake

That's not a tight bound though.

What do you mean by the above?

Blake · #4 23-Jun-2006, 13:19

If g(z) is a function, a tight bound on g is a function f(z) such that there exists constants c1 and c2 with c1f(z) < g(z) < c2f(z) for all z sufficiently large. In this case, for nk, we can find c2 but not c1.

Jokky · #5 03-Jul-2006, 20:17

I came up with the answer

f(n) = 0( m * n )

Would that be correct?

Blake · #6 03-Jul-2006, 20:19

What is m?

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Preferred program for audio input analysis	e30	C++ Forum	2	11-Jun-2006 16:56
conversion double to float	donaldk	C Programming Language	5	12-Feb-2006 23:16
hashing help	saiz66	C++ Forum	1	06-Jul-2004 06:16
Script needed for letting user input a few days of data for tracking and analysis.	tradertt	MySQL / PHP Forum	3	06-Mar-2003 02:54

Complexity Analysis

Re: Complexity Analysis

Re: Complexity Analysis

Re: Complexity Analysis

Re: Complexity Analysis

Re: Complexity Analysis