C++

Forum

 
Big O Notation

Masada (14)
I'm just working through some exercises trying to understand Big O Notation and would like to know if I have the correct answers to this. Any feedback is appreciated. Thank you.

This one I called O(n)
1
2
3
4
5
6
 
  int function computation(int result, int n)
{
   for (int i = 3; i <= n; ++i)
       result += i * n;
   return result;
}


This one I came up with O(n^2)
1
2
3
4
5
6
 
void function tables(int k)
{
for (int i = 0; i < k; ++i)
   for (int j = 0; j <= k; ++j)
       a[i] += a[j] + i + j;
}


This one O(n)
1
2
3
4
5
6
7
 
long factorial (int n)
{
    if (n < = 1)
        return 1;
    else
       return n * factorial (n - 1);
}


This one O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
bool DoublyList::search(const int& searchData) const
{
bool found = false;
Node *current;
current = first;
while (current != NULL && !found)
{
    if (current->getData() == searchData)
           found = true;
    else
          current = current->getNextLink();
}
return found;
}


This one O(n log n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void modifyArray(int a[], int size, int item)
{
int max = a[0];
for (int i = 1; i < size / 2; ++i)
{
      if (max < a[i])
           max = a[i];
}
for (int j = 1; j <= size; ++j)
{
      ++max;
      cout << max;
}
}


This one O(n^2)
1
2
3
4
5
6
7
8
9
10
11
 
void doSomething(int n)
{
      for (int k = 1; k <= n / 2; ++k)
{
      cout << (k * k) << endl;
      for (int j = 1; j <= n; ++j)
{
      cout << (n * n * n * n) << " ";
}
}
}


This one O(log n)
1
2
3
4
5
6
7
 
bool myFunction (int k)
{
int x = k + 2;
while (x > 1)
    x /= 2;
return (k > x);
}


This one O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
 
bool anotherFunction(const vector<int>& v1)
{
if (v1.size() == 0)
return false;
else
{
for (unsigned int i = 0; i < v1.size() - 1; ++ i)
for (unsigned int j = v1.size()/2; j < v1.size() - 1; ++j)
       if (v1[i] != v1[j+1])
           return true;
}
return false;
}


This one O(n log n)
1
2
3
4
5
6
7
8
9
10
11
12
 
void thisFunction(int n)
{
 for (int k = 0; k < n; ++k)
{
     j = n;
while (j > 0)
{
      cout << j << " ";
      j /= 2;
}
}
}
Last edited on
ne555 (10692)
learn to indent.
Explain void modifyArray(int a[], int size, int item) that you say it is O(n lg n)
Masada (14)
I guess when I saw the /= 2 in the first for loop, I was thinking log n. Now that I think about it, that exercise is probably just O(n). But I'm not sure, that is why I'm looking for any confirmation if this is right or not. I didn't realize the code was not indented, sorry about that. Thank you.
ne555 (10692)
your code still is not properly indented.

> But I'm not sure, that is why I'm looking for any confirmation
Unless you provide some rationale, you may as well just guess.
Topic archived. No new replies allowed.