-
Notifications
You must be signed in to change notification settings - Fork 57
/
Copy pathcodeanalysis.cc
70 lines (61 loc) · 1.36 KB
/
codeanalysis.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// O() omega()
int func1(int n) {
for (int i = n-1; i > 0; i--)
if (i % 17 == 0)
return i;
return 0;
}
//O() omega()
int func2(int n) {
int sum = 4;
for (int i = n-1; i > 0; i--)
for (int j = 0; j < i + 3; j++)
sum += 3;
return sum;
}
// Q: can you write func2 more efficiently?
int func3(int n) {
int sum = 0;
for (int i = 1; i <= n; i++)
sum += i;
return sum;
}
//Q: can you write func3b more efficiently?
//Q2: is this more efficient than func3?
int func3b(int n) {
int sum = 1;
for (int i = 2; i <= n; i++)
sum += i;
return sum;
}
// see: https://en.wikipedia.org/wiki/Perfect_number
// should return true if the number is perfect, false otherwise.
// this code is wrong. It is also horribly inefficient.
// can you make it better?
// it should return true if the parameter is perfect.
bool perfect(int n) {
int sum = 0;
for (int i = 1; i <= n; i++)
if (n % i == 0)
sum += i;
return sum == n;
}
double fact(int n) {
double p = 1;
for (int i = 1; i <= n; i++)
p *= i;
return p;
}
// Q: What is the complexity?
// Q2: can you make one faster, perhaps using memoization?
double choose(int n, int r) {
return fact(n) / (fact(r) * fact(n-r));
}
// Do this test more efficiently
bool countPrimesProb(uint64_t a, uint64_t b) {
uint32_t count = 0;
for (uint64_t i = a; i <= b; i++)
if (isPrime(i))
count++;
return (b - a + 1) / count <= 2;
}