2
votes
4answers
46 views

Prove that $3^n$ is not $O(2^n)$.

I am working on some Big oh questions and I can't seem to get how disprove them. In this case we have: Prove that $3^n$ is not $O(2^n)$ I can see that its obvious just by looking at the two ...
0
votes
1answer
23 views

Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$, where $0 < a < b$.

Let $a$ and $b$ be real numbers such that $0 < a < b$. Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$.
0
votes
0answers
22 views

Question about set and series notation in the GSP Algorithm

I tried this in programming forums with no luck and since my primary issue is with the notation, I'm asking here: I have the definition of the GSP Algorithm: Definition However I don't understand ...
0
votes
1answer
30 views

Reading set notation for the flow number

Could someone please help me to understand the following notation: Flow Number: In case of need, S refers to a set of flows, C(s) is called congestion and D(S) is dilation. How would you put in ...
0
votes
1answer
25 views

Understanding the definition of the d-dimensional Hyperube

Please see the picture bellow about the definition of the nodes of the d-dimensional Hypercube. Could anyone please tell me what does that notation means. I get confused with the superscript after the ...
0
votes
0answers
15 views

chained max notation

I'm confused on how to implement a quality indicator for multi-objective optimization. I don't understand the following notation. $$I_{\epsilon} (A,B)=\max_{z^2 \in B} \min_{z^1 \in A} \max_{1 \le i ...
0
votes
0answers
22 views

Notation help: “linearizing” multidimensional indices

I have an algorithm that makes use of a multidimensional data structure, e.g. $A(i,j,k)$, $1\le i,j,k\le n$. I am looking for a simple notation that enables me to refer to the $\ell$'th elements of ...
0
votes
1answer
111 views

Time complexity in terms of theta notation [duplicate]

sum= 0; for (i = n; i > o; i = i/3) for (j = 0; j < n^3; j++) sum++; what is the time complexity (in Θ- notation) in terms of n? so far, i've gotten to this point: The ...
-1
votes
1answer
196 views

Time complexity function in terms of theta notation

sum = 0; for (i = 0; i < n; i++) for (j = 1; j < n^3; j = 3*j) sum++; what is the time complexity (in $\Theta$-notation) in terms of ...
2
votes
3answers
159 views

What does 'i-th' mean?

I have seen a problem set for the tower of hanoi algorithm that states: Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is ...
6
votes
2answers
5k views

Difference between formula and algorithm

What is the difference between the terms formula and algorithm in mathematics? I haven't seen the definition of formula anywhere. I know that algorithm means that Turing machine halts for every input. ...
0
votes
1answer
69 views

Why is the upper bound of this statement always incremented by 1?

Why is "for j = 1 to n" translate to this? Why is the upper bound always incremented by 1? $$\sum_{j=1}^{n+1}1 $$ Why isn't it $$\sum_{j=1}^n1 $$ "for j = 1 to n" is written in pseudo code btw ...
1
vote
0answers
229 views
0
votes
1answer
111 views

Is there a term for $O( (m+n) \log{mn})$ time algorithms?

Is there a term for $O( (m+n) \log{mn})$? I remember seeing it often in some context but can't remember.
0
votes
0answers
220 views

How to write a mathematical formula for the given statment?

I would like to know how to present the following statement in mathematical form: A is a object which representing by points, for instance 150 points. B is another object, also present by points. I ...
0
votes
2answers
1k views

Big O Notation and finding witnesses

I am trying to figure out some stuff here with Big O Notation. I mean I understand the concept of it and can generally be able to tell what the efficiency of something is, but I do not really ...
2
votes
3answers
401 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
0
votes
1answer
428 views

Represent loop nests as multiple summations?

This may be trivial but I would appreciate if someone could point me in the right direction here.. I am trying to express the number of instances in a loop nest in a general form. As a mathematical ...
1
vote
1answer
93 views

What does it mean for a function to be part of a set in O-notation?

I'm trying to understand the concepts underlying the O-notation. The formal definition is: $ O(g(n)) = \{ f(n) \textrm{ such that there exist positive constants }c\textrm{ and }n_{0} \textrm{ such ...
0
votes
3answers
190 views

confusing in SEAL (Software-Optimized Encryption Algorithm) mathematic notation

I'm developing an encryption software based on SEAL algorihm for my research. I found the paper in here My Question is what is the meaning of $$ H_{i \operatorname{mod} 5}^i $$ in page 5? ...
0
votes
3answers
982 views

What does this notation mean: $\lg^{\ast} n = \min \{ i \ge 0 \,:\, \lg^i n \le 1 \}$?

For my algorithms course I am studying the definition of the iterated logarithm function (and functional iteration in general) and I don't quite understand the set notation used (it's been quite a few ...
2
votes
1answer
236 views

variable update operator , using “correct” mathematical notation

In a text describing mathematically an algorithm, there is a vector $y_l$ (local y-axis) which is computed, but must be subsequently adjusted to avoid numerical drift. I've considered a few ...
2
votes
0answers
107 views

What does it mean if a sequence is indexed beyond its bounds?

I'm looking at a paper (On Base and Turyn Sequences by C. Koukouvinos, S. Kounias and K. Sotirakoglou) that describes an algorithm for finding specific sequences. Part of the algorithm involves ...
0
votes
1answer
535 views

How to describe an algorithm with mathematical notation?

I often have to create new computer science algorithm. The problem come when I have to describe them in a scientific way. I don't know where I should look for to learn how to describe my algorithms ...
3
votes
1answer
795 views

Determine if function is little-o, little-omega or big-theta

Let $f(n) = n^3(5+2\cos(2n))$ and $g(n) = 3n^2+4n^3+5n$. Given these two functions, I must determine the appropriate symbol where the underscore is: $f(n) \in \_(g(n))$ So, first thing to do is take ...
1
vote
1answer
76 views

Any concise way to represent this in a formula?

I'm doing a presentation and I have to include this in it: for j in 1..j_max b_offset = copy(b) b_offset[j] = b_offset[j] + 1 I can't do b_offset = b + ...