Problem with the complexity of the program

[bandrei2408]

Hello ! I need your help to calculate the complexity of a program. I need this for my exam and i can't understand how it is calculated. I've tried searching for solutions on google and reading about it but i still can't get it. Maybe if someone can calculate it for me on an example it will be more easy for me to undestand. I must admit i've never done this before, so i would love to take it easy. The problem asks to create a program with the complexity O(n) and i wonder if the program i made is a O(n) complexity.

Here is the code :

#include <iostream.h>

int ver(int a){
while(a%2==0)
a=a/2;
while(a%3==0)
a=a/3;
while(a%5==0)
a=a/5
if(a==1)
return 1;
else
return 0;}

void main(){
int n,i;
i=1;
cin>>n;
cout<<endl;
while(n!=0){
if(ver(i)==1){
cout<<i<<" ";
n--;}
i++;}}

If you can give me some clues about how should i calculate it , i would be very happy cause i have my exam in 1 week and i still can't do this thing. I can solve the problems i need for my exam i just can't calculate their complexity cause no one ever explained this to me and i can't find it on the internet. I would be very glad if you can give me some examples or atleast calculate the complexity of this program for me and explain how you did it. I need it based on n.

Thanks in advance,
Andrew

[Alexeala]

i don't know how to solve your problem...u see...i like fisics...those kind of problems are to hard for me...but maybe if u call SMINTINA RODICA you will be able to understand..she is the best..good luck buddy..

[bandrei2408]

Thanks for trying to help ! Good luck with your physics :) !

[teo236]

The program tries, with the number of times entered, make that "i" becomes a multiple of 2, 3 and 5 at a time. "i" will autoincrement in each cycle of "while". The while loop is repeated "n" times.

the last while...

while(n!=0){
...
n--;}
...}

is the same as the loop for:

for(n;n>0;n--){
...
}

[arkoenig]

You say: "The problem asks to create a program with the complexity O(n) and i wonder if the program i made is a O(n) complexity."

A program with complexity O(n) that does what?

[bandrei2408]

I have to find first n numbers in increasing order in this heap M = { (2^x)*(3^y)*(5^z) | x,y,z are natural number >= 0 }.

[arkoenig]

Here you go.

Usually I don't do people's homework for them, but this solution is part of the public literature, and if you actually read and understand it, you will have learned as much as if you had solved it yourself. Perhaps more, because the exposition is so elegant.

[bandrei2408]

Thanks for your help. Well it's not about my homework, I just wanted to learn more about the big O notation. A friend explained it to me so now i got it. Thanks again!