Scribd
Upload
286 views3 pages

DSA Lab 03

This document describes a student's lab assignment to analyze the time complexity of two algorithms for determining if a number is prime. It provides the source code for two prime number checking functions, one that checks all numbers from 2 to n-1, and one that checks only up to the square root of n. The document records the output of running both functions on various input numbers and calculates the time complexity of each to determine which is more efficient.

Uploaded by

Atif Jalal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
286 views3 pages

DSA Lab 03

This document describes a student's lab assignment to analyze the time complexity of two algorithms for determining if a number is prime. It provides the source code for two prime number checking functions, one that checks all numbers from 2 to n-1, and one that checks only up to the square root of n. The document records the output of running both functions on various input numbers and calculates the time complexity of each to determine which is more efficient.

Uploaded by

Atif Jalal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Atif Jalal

02-235191-027
BS (IT)-3A Lab 03: Measurement of Time Complexity of an algorithm Date: 10 July, 2020

Task 1:

Source Code:
#include<iostream>
#include<math.h>
using namespace std;
void P1(int n)
{
int b=0,count=0;
for(int i=2;i<=n-1;i++)
{
if(n%i==0)
{
b=1;
}
count++;
}
if(b==1)
{
cout<<"Not a Prime Number "<<count<<endl;
}
else
{
cout<<"Prime Number "<<count<<endl;
}

}
Atif Jalal
02-235191-027
BS (IT)-3A Lab 03: Measurement of Time Complexity of an algorithm Date: 10 July, 2020
void P2(int n)
{
int b=0,count=0;
for(int i=2;i<=sqrt((int)n);i++)
{
if(n%i==0)
{
b=1;
}
count++;
}
if(b==1)
{
cout<<"Not a Prime Number "<<count;
}
else
{
cout<<"Prime Number "<<count<<endl;
}
}
int main()
{
int a;
cout<<"Enter a Number: ";
cin>>a;
P1(a);
P2(a);
system("pause");
}

Output:
Atif Jalal
02-235191-027
BS (IT)-3A Lab 03: Measurement of Time Complexity of an algorithm Date: 10 July, 2020
Task 2:
Calculate times taken by these programs for given values and conclude which algorithm is better
than other
i. n = 11
ii. n = 101
iii. n=1000003
iv. n = 10000000019
Note: Let’s assume computer takes 1 mili-second for division operation. In the worst case first
algorithm loop will exactly (n-2) times or (n-2) division and in second algorithm (√n – 1) times

Output:

You might also like