1,105,177 Community Members

How to Find Time Complexity

Member Avatar
himgar
Light Poster
38 posts since May 2008
Reputation Points: -4 [?]
Q&As Helped to Solve: 3 [?]
Skill Endorsements: 0 [?]
 
0
 

I have implemented Bubble Sort. How to add counters in the program so that I can calculate and display the Best Case, Worst Case & Average Case Time Complexity of this program?

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n);
int compb = 0, compw = 0;

int main()
{
	int arr[20], arr1[20], n, i;

	cout << "Enter the Size of Array: ";
	cin >> n;
	cout << "\nEnter the Elements of Array: ";
	for(i = 0; i < n; i++)
	{
		cin >> arr[i];
		arr1[i] = arr[i];
	}
	
	bubbleSort(arr, n);

	cin.get();
	cin.ignore();
	return 0;
}

void bubbleSort(int arr[], int n)
{
	int i, j, temp;
	
	for(i = 0; i < n; i++)
	{
		compb++;
		for(j = 0; j < n - 1; j++)
		{
			if(arr[j] > arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			   compa++;
			}
			 compw++;
			
		}
	}
	cout << "\nSorted Array using Bubble Sort: ";
	for(i = 0; i < n; i++)
	{
		cout << arr[i];
	}
}
Member Avatar
grh1107
Newbie Poster
18 posts since Nov 2011
Reputation Points: -4 [?]
Q&As Helped to Solve: 2 [?]
Skill Endorsements: 0 [?]
 
0
 

For bubble sort you just have to count the number of iterations, there is software that can compute the time complexity

however http://en.wikipedia.org/wiki/Sorting_algorithm will solve the problem of best case worse case and average senario

best 0(n)
average 0(n^2)
worst O(n^2)

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article