path: root/01-07.md

[\<- 01/05](01-05.md)

---

## Use Standard Library

```
#include <iostream>
```

- To use a function from `iostream`, need to specify the `std::___` namespace (since iostream belongs to the std namespace)
- To avoid having to write `std::` behind the `iostream` functions, you can write at the top `using namespace std;`
	- You can have multiple `using namespace` specifications
	- If a function name belongs to multiple namespaces that are called at the top (and each take the same number of parameters), this can lead to issues

---

## Preconditions and Postconditions

### Defining a Function

```
//example function definition for a function that squares an integer
int square(int A){
	return A*A;
}

int B = square(2); //B will equal 4
```

### Specifying Pre and Post conditions

- Preconditions - What must be true before calling your program/method
- Postconditions - What must be true/what will happen after your program returns

- For the above function:
	- Preconditions
		- None (it is implied that the input must be an integer)
	- Postconditions
		- If precondition is satisfied, postcondition must be true

### Examples

```
double get_sqrt(double A);
//preC  A >= 0 : input has to be a double and non-negative
//postC returns square root of integer
```

- What will happen if the user calls the following:

```
get_sqrt(-1);
```

- The program will not work, it may even crash!
	- Preconditions are important so that users know how to use the function without breaking it

```
void print_name(char *A);
//preC  input has to be an array of characters (and non-NULL)
//preC  array must be null-terminated ('\0' at the end)
//postC print the input to stdout with no spaces
```

### Assert

- the `assert()` function can be used to enforce preconditions
- Example:

```
double get_sqrt(double A){
	assert(A >= 0); //to enforce precondition

	//body of the program goes here
}
```

- Alternative example without using `assert()`

```
double get_sqrt(double A){
	if(A < 0){
		//print error message and exit
	}

	//body of the program goes here
}
```

- Detailed C++ Example

```
#include <iostream>
// uncomment to disable assert
// #define NDEBUG
#include <cassert>

int main(){
	assert(10 + 10 == 20);
	std::cout << "Execution continues past the first assert\n";

	assert(12+12 == 20);
	std::cout << "Execution continues past the second assert\n";
}
```

### Static Assert

- Static assert are all checked at compile time, rather than just whenever the program that the assert is called in is called
	- `static_assert(A > 0)`

- Detailed C++ Example

```
void foo(int *a){
	assert(a != NULL);
	std::cout << *a << std::endl;
}

void bar(int *a){
	static_assert(sizeof(a) == 8, "I can only compile on a 64-bit architecture!"); //to make sure the code is only compiled on a 64-bit architecture
}

int main(int argc, const char *argv[]){
	int *a = new int(4);
	foo(a);
	bar(a);

	return 0;
}
```

### Advantages of Using Preconditions and Postconditions

- Succinctly describes the behavior of a function without cluttering up your thinking with details of how the function works
- At a later point, you may reimplement the function in a new way but programs (which only depend on the precondition/postcondition) will still work with no changes.

---

## Time Analysis

### What is Time Analysis?

- How fast the system is running
- How fast the algorithm is executed
	- How many clock signals does it take
- Is it the algorithm's fault?

### Time Analysis?

- Time is a parameter that needs to be optimized!
	- Time is $
	- Some problems are interactable
	- Scalability
- Is it better to be faster?
	- YES! - time is money!
	- NO! - not always (for example, real time applications)

### How to do Time Analysis?

- Count the number of operations
- How??

```
int *add_array(int *array1, int *array2, int N){
	for(i = 0; i<N, i++){
		array1[i] += array2[i];
	}

	return array1;
}
```

- Number of operations depends on the input size

### Big-O Notation

- Declares the ORDER of the number of operations
- O(1), O(n), O(n^2)

### Various Big-O Notation

|Complexity|Function|Common name |
|----------|--------|------------|
|Highest   |n!      |factorial   |
|          |2^n     |exponential |
|          |n^d, d>3|polynomial  |
|          |n^3     |cubic       |
|          |n^2     |quadratic   |
|          |nsqrt(n)|            |
|          |nlog(n) |quasi-linear|
|          |n       |linear      | 
|          |sqrt(n) |root - n    | 
|          |log(n)  |logarithmic |
|Lowest    |1       |contsant    |

### Examples

|T(n)                |Complexity|
|--------------------|----------|
|5n^3 + 200n^2 + 15  |O(n^3)    |
|3n^2 + 2^300        |O(n^2)    |
|5log2(n) + 15ln(n)  |O(log(n)) |
|2log(n^3)           |O(log(n)) |
|4n + log(n)         |O(n)      |
|2^64                |O(1)      |
|log(n^10) + 2sqrt(n)|O(sqrt(n) |
|2^n + n^1000        |O(2^n)    |

### Big-O Comparisons

- Different ways to solve a problem -> different complexity

### Examples

```
for(i = 0; i<N; i++){
	statement;
}

O(N)
```

```
for(i = 0; i < N; i++){
	for(j = 0; j < N; j++){
		statement;
	}
}

O(N^2)
```

```
for(int i = 1; i <= n; ++i){
	for(int j = 1; j <= i; ++j){
		statement;
	}
}

O(?) (to be continued...)
```

### Best Case/Worst Case Scenario

```
bool search(vector<int> arr, int item){
	for(i = 0; i < arr.size; i++){
		if(arr[i] == item){
			return true;
		}
	}

	return false;
}

//if vector<int> arr{1, 2, 3, 4, 5}
search(arr, 1); //O(1) -> Best Case
search(arr, 5); //O(N) -> Worst Case
```

[01/12 ->](01-12.md)