User Tommy_Shan - Olympiads Online Judge | DMOJ

User Tommy_Shan

From Olympiads School, Richmond Hill H.S., STEM Yard

About

书山有路勤为径，学海无涯苦作舟。

Time Complexity Guide

Range	Time Complexity
$n \leq 10$ ~n \leq 10~	$\mathcal{O}(n!)$ ~\mathcal{O}(n!)~
$n \leq 20$ ~n \leq 20~	$\mathcal{O}(2^{n})$ ~\mathcal{O}(2^{n})~
$n \leq 50$ ~n \leq 50~	$\mathcal{O}(n^{5})$ ~\mathcal{O}(n^{5})~
$n \leq 100$ ~n \leq 100~	$\mathcal{O}(n^{4})$ ~\mathcal{O}(n^{4})~
$n \leq 500$ ~n \leq 500~	$\mathcal{O}(n^{3})$ ~\mathcal{O}(n^{3})~
$n \leq 3000$ ~n \leq 3000~	$\mathcal{O}(n^{2}\cdot \log{n})$ ~\mathcal{O}(n^{2}\cdot \log{n})~
$n \leq 5000$ ~n \leq 5000~	$\mathcal{O}(n^{2})$ ~\mathcal{O}(n^{2})~
$n \leq 10^{5}$ ~n \leq 10^{5}~	$\mathcal{O}(n\cdot \log{n}) \sim \mathcal{O}(n\cdot \sqrt{n})$
$n \leq 10^{6}$ ~n \leq 10^{6}~	$\mathcal{O}(n\cdot \log{n}) \sim \mathcal{O}(n)$
$n \leq 10^{12}$ ~n \leq 10^{12}~	$\mathcal{O}(\sqrt{n})$ ~\mathcal{O}(\sqrt{n})~
$n \leq 10^{18}$ ~n \leq 10^{18}~	$\mathcal{O}(\log{n})$ ~\mathcal{O}(\log{n})~

Type	Range	Memory (Byte)
$\texttt{char}$ ~\texttt{char}~	$-127$ ~-127~ to $127$ ~127~ or $0$ ~0~ to $255$ ~255~	$1 \ \texttt{byte}$ ~1 \ \texttt{byte}~
$\texttt{bool}$ ~\texttt{bool}~	$\texttt{true}$ ~\texttt{true}~ or $\texttt{false}$ ~\texttt{false}~	$1 \ \texttt{byte}$ ~1 \ \texttt{byte}~
$\texttt{short int}$ ~\texttt{short int}~	$-32768$ ~-32768~ to $32767$ ~32767~	$2 \ \texttt{byte}$ ~2 \ \texttt{byte}~
$\texttt{unsigned short int}$ ~\texttt{unsigned short int}~	$0$ ~0~ to $65535$ ~65535~	$2 \ \texttt{byte}$ ~2 \ \texttt{byte}~
$\texttt{wchar_t}$ ~\texttt{wchar_t}~	$1 \ \texttt{wide character}$ ~1 \ \texttt{wide character}~	$2 \ \texttt{byte}$ ~2 \ \texttt{byte}~
$\texttt{int}$ ~\texttt{int}~	$-2147483648$ ~-2147483648~ to $2147483647$ ~2147483647~	$4 \ \texttt{byte}$ ~4 \ \texttt{byte}~
$\texttt{unsigned int}$ ~\texttt{unsigned int}~	$0$ ~0~ to $4294967295$ ~4294967295~	$4 \ \texttt{byte}$ ~4 \ \texttt{byte}~
$\texttt{float}$ ~\texttt{float}~	$6 \ \texttt{decimal digits precision}$ ~6 \ \texttt{decimal digits precision}~	$4 \ \texttt{byte}$ ~4 \ \texttt{byte}~
$\texttt{long int}$ ~\texttt{long int}~	$-2147483648$ ~-2147483648~ to $2147483647$ ~2147483647~	$8 \ \texttt{byte}$ ~8 \ \texttt{byte}~
$\texttt{unsigned long int}$ ~\texttt{unsigned long int}~	$0$ ~0~ to $4294967295$ ~4294967295~	$8 \ \texttt{byte}$ ~8 \ \texttt{byte}~
$\texttt{long long int}$ ~\texttt{long long int}~	$-2^{63}$ ~-2^{63}~ to $2^{63}-1$ ~2^{63}-1~	$8 \ \texttt{byte}$ ~8 \ \texttt{byte}~
$\texttt{unsigned long long int}$ ~\texttt{unsigned long long int}~	$0$ ~0~ to $2^{64}-1$ ~2^{64}-1~	$8 \ \texttt{byte}$ ~8 \ \texttt{byte}~
$\texttt{double}$ ~\texttt{double}~	$15 \ \texttt{decimal digits precision}$	$8 \ \texttt{byte}$ ~8 \ \texttt{byte}~
$\texttt{long double}$ ~\texttt{long double}~	$18 \ \texttt{decimal digits precision}$	$12 \ \texttt{byte}$ ~12 \ \texttt{byte}~

Memory Unit	Byte
$1 \ \texttt{KB}$ ~1 \ \texttt{KB}~	$1024 \ \texttt{byte}$ ~1024 \ \texttt{byte}~
$1 \ \texttt{MB}$ ~1 \ \texttt{MB}~	$1048576 \ \texttt{byte}$ ~1048576 \ \texttt{byte}~
$1 \ \texttt{GB}$ ~1 \ \texttt{GB}~	$1073741824 \ \texttt{byte}$ ~1073741824 \ \texttt{byte}~

Approximate the memory used for an array: $\frac{\texttt{total number of cells} \ \times \ \texttt{data type memory in byte}}{10^6}$ .

Rating history