# Untitled

unknown
c_cpp
2 months ago
6.0 kB
3
Indexable
Never
```///SEMINAR 1: 24/2/2024
#include <iostream>
#include <vector>
// Some questions:
///Seminar 1 - Time Complexity
/// What is an algorithm ?
///==>Algorithm: Input ===> |Algorithm| ===> Output
/// Time complexity ? Why ?
///==> Because  computers have different configuration, it's not useful to judge a program by running time.
/// For example :
int SumUp(int size) {
int sum = 0; // 1
for (int i = 0; i < size; i++) { //2n
sum = sum + i; //3n
}
return sum; // 1
}
/// ===> T(n) = 2 + 5n  ==> O(n) = ??
/// The dominant term is the term the one that gets biggest (i.e. dominates) as N gets bigger.
/// Example: n^3 grow faster than n^2
/// Big O notation: f(n) = O(g(n)) ==> limit of f(n)/g(n) with n tend to infinity < infinity or exist n_0, c > 0
/// such that for all n > n_0 f(n) <= c*g(n)
/// Ex: f(n) = n^5 + n^4 + n^3 ===> f(n) ~ O(n^5)
/// Ex: f(n) = n*log(n) + n ===> f(n) ~ O(n*log(n))
/// Ex: f(n) = 2*n + n^(0,5) + n ^ (1,5) ===> f(n) ~ O(n^(1,5))
/// Let's calculate time complexity of following code:
//code 1:
bool isEven(int value) {
return (value % 2 == 0);
}
/// O(1) Because you're only ever taking one value, there is no "loop" to go through.
///Even as the value gets bigger, you simply divide it by 2 and see whether it returns an integer or a float.

//code 2:
bool areYouHere(const std::vector<int>& arr1, const std::vector<int>& arr2) {
for (size_t i = 0; i < arr1.size(); i++) {
for (size_t j = 0; j < arr2.size(); j++) {
if (arr1[i] == arr2[j]) return true;
}
}
return false;
}
/// O(n^2) because u will go through each array once.
///

//Code 3:
void doubleArrayValues(std::vector<int>& array) {
for (size_t i = 0; i < array.size(); i++) {
array[i] *= 2;
}
}
/// O(n) Reasoning: As `array.length` increases, the number of iterations increases at the same rate.
///This is because you don't have to loop any more than once: however many items are in the array
///is how many times you run the function.

//Code 4:
int naiveSearch(const std::vector<int>& array, int item) {
for (size_t i = 0; i < array.size(); i++) {
if (array[i] == item) {
return i;
}
}
return -1;
}

///O(n) Answer: O(n). Linear run time complexity.
///Reasoning: Same as above with the doubler. You have to check each and every item once and only once
///in order to determine whether you've got a match.

//Code 5:
int calculateY(int n) {
int y = 0;
for (int j = 1; j * j <= n; j++) {
y++;
}
return y;
}
///O(√n) because
/// j is still growing linearly, but the loop runs as long as j2 ≤ n. This means that as soon as j exceeds √ n, it will stop
///Therefore, there will only be O(√n) iterations of the loop, and since each one does O(1) work, the total work done is O(√n).

//Code 6:
int efficientSearch(const std::vector<int>& array, int item) {
int minIndex = 0;
int maxIndex = static_cast<int>(array.size()) - 1;
int currentIndex;
int currentElement;

while (minIndex <= maxIndex) {
currentIndex = (minIndex + maxIndex) / 2;
currentElement = array[currentIndex];

if (currentElement < item) {
minIndex = currentIndex + 1;
} else if (currentElement > item) {
maxIndex = currentIndex - 1;
} else {
return currentIndex;
}
}
return -1;
}
///O(logn)

//Code 7:
void nestedLoopsFunction(int n) {
int b = 0; // constant
for (int i = n; i > 0; i--) { // n iterations
for (int j = 0; j < i; j++) { // runs i times in each iteration
b = b + 5;
}
}
std::cout << b << std::endl;
}
/// The outer loop runs from n to 1, decrementing i by 1 in each iteration.
/// The inner loop runs i times in each iteration of the outer loop.
/// The total number of iterations for the inner loop can be expressed as the sum of the first n positive integers:  n+(n−1)+(n−2)+…+1
/// This sum is known as the arithmetic series sum and is equal to n*(n+1)/2
///  the inner loop has a time complexity of O(n^2)

//Code 8:
///You are given two arrays a and b sorted in non-decreasing order and a number S.
///Find such i and j such that the sum a[i] + b[j] = S. Time O(n).

std::pair<int, int> findPairsWithSum(const std::vector<int>& a, const std::vector<int>& b, int S) {
int i = 0; // Pointer for array a (starting from the beginning)
int j = b.size() - 1; // Pointer for array b (starting from the end)

while (i < a.size() && j >= 0) {
int currentSum = a[i] + b[j];

if (currentSum == S) {
// Found a pair with the given sum
return std::make_pair(a[i], b[j]);
} else if (currentSum < S) {
// Move the pointer in array a to the right to increase the sum
i++;
} else {
// Move the pointer in array b to the left to decrease the sum
j--;
}
}

// No pair found with the given sum
return std::make_pair(-1, -1);
}

//Code 9:
/// You are given two arrays a and b sorted in non-decreasing order. Find the number of pairs (i, j)
///such that a[i] = b[j] . Time O(n).

int countEqualPairs(const std::vector<int>& a, const std::vector<int>& b) {
int count = 0;
int i = 0; // Pointer for array a
int j = 0; // Pointer for array b

while (i < a.size() && j < b.size()) {
if (a[i] == b[j]) {
// Found a pair (i, j) with ai = bj
count++;

// Move both pointers to the next elements
i++;
j++;
} else if (a[i] < b[j]) {
// Move the pointer in array a to the right
i++;
} else {
// Move the pointer in array b to the right
j++;
}
}

return count;
}```