Can we say that Mathematically the time complexity of the code in python is better than that of C?

Question

The python code for printing a diamond pattern is :

def main():
n= input('The size of the diamond :: ')    
a=n
for i in range(n):
        print ' '*a,'*'*(2*i-1)
        a=a-1

a=0
p=n
for i in range(n):
        print ' '*a,'*'*(2*p-1)
        a=a+1
        p=p-1

main()

for a similar output the code in C is ::

#include<stdio.h>
int main()
{
   int i,j;
   int n;
   printf("---PATTERN---\n");
   printf("enter the number of rows :: \n");
   scanf("%d",&n);
   for(i=0;i<=n;i++)
   {
       for(j=n;j>i;j--)
        {
           printf(" ");
        }
       for(j=0;j<2*i+1;j++)
       {
          printf("*");
       }
       printf("\n");
   }
    i=0;
   for(i=0;i<=n;i++)
   {

       for(j=0;j<i;j++)
       {
          printf(" ");
       }
       for(j=2*n-1;j>=2*i-1;j--)
       {
          printf("*");
       }
    printf("\n");
 }

return 0;
}

My Question is : Can we say that Mathematically the time complexity of the code in python is better than that of C? Although the Run time of the C program is less than that of Python but the same program in Python does not involve nesting of loops as in the case of C can we say that structurally Python is a more efficient language? -my apologies if the doubt sounds stupid.

Could you please make your python code syntactically valid? But no, there is no magic to make python more "efficient". — juanchopanza, Jun 09 '14 at 08:16
`print ' '*a,'*'*(2*i-1)` here are your nested loops. Remember that, even if you hide complexity behind a simple statement, it's not like it goes away. In Python you can parse an XML file/apply a regex/launch a rocket to the moon with a single statement, but that doesn't make it O(1). — Matteo Italia, Jun 09 '14 at 08:17
In KerrekScript 2.0, you can would say `print '*'<>n`, so the complexity there is O(1). (It turned out that the built-in diamond operator *really* propelled the language out of obscurity and into the mainstream.) — Kerrek SB, Jun 09 '14 at 08:20
@juanchopanza sorry sir jst copied the code from IDLE so the indentation was lost — Durwasa Chakraborty, Jun 09 '14 at 08:26
@KerrekSB Thankyou sir bt I ll have to undergo a lot of reading before I understand your answer. Im a complete novice when it comes to programming :) — Durwasa Chakraborty, Jun 09 '14 at 08:31
*Can we say that Mathematically the time complexity of the code in python is better than that of C?* No. — David Heffernan, Jun 09 '14 at 08:32
You can edit the question to fix the indentation. And you don't need to call me "sir" :-) — juanchopanza, Jun 09 '14 at 08:36

score 4 · Answer 1 · answered Jun 09 '14 at 08:17

4

The nested loops on Python are just not so easy to see. The statement print ' '*a,'*'*(2*i-1) is also a loop (in fact one loop per "multiplication") – how else would you be able to do a variable amount of repeated work? It's just not a loop that you spell out.

answered Jun 09 '14 at 08:17

Kerrek SB

464,522
92
875
1,084

On analyzing the the python code given in the question by disassembling it to bytecode (using dis), the operation involved between `' '` and `a` ( inside `print ' '*a,'*'*(2*i-1)`) is given as `BINARY_MULTIPLY`. I'm not saying that there is no nested loop involved but just want to ask that if this `BINARY_MULTIPLY` is yet another layer of abstraction and under the hood there's a loop involved ? – Vipul Jun 09 '14 at 11:44
@Vipul: Are you sure you're noot looking at the `2*i` part? – Kerrek SB Jun 09 '14 at 12:22
Yes !! I'm absolutely sure.. actually there are 3 `BINARY_MULTIPLY` : 1st for `' '*a` 2nd for `'*'*(2*i-1)` and 3rd for `2*i` part. What is actually happening here? I cannot post the disassembled code here – Vipul Jun 09 '14 at 12:38

score 4 · Accepted Answer · edited May 23 '17 at 12:05

Can we say that Mathematically the time complexity of the code in python is better than that of C?

No, you cannot. The time complexity of a code with regards to a machine (even theoretical ones) depends on what the machine ultimately does (time spent solving the problem) and not how you tell on what to do i.e. C and Python are two, amongst many, ways to tell to it what to do. However, I'd recommend you to compile the Python code to C and then check it against your C program, by which you'll be comparing apples to apples and not to oranges. Even better, compile (and link) them both into binaries and disassemble them to verify your assumptions to see that both does in fact loop.

Python does not involve nesting of loops

That's just syntactic sugar that Python as a language provides; however, under the hood, it'd loop too, like the other answers mention.

can we say that structurally Python is a more efficient language?

No again, because structure is a matter of style and not efficiency.

If you're taking about performance (time) or memory efficiency, then it's not an inherent nature of the language itself but of an implementation of the language and how well it performs on given architectures; this again should be measured and not assumed/guessed. For instance, take Lua, the same language has different interpreters (implementations), of which a few are remarkably faster than the others. So efficiency is a matter of implementation and not the language itself.

score 1 · Answer 3 · answered Jun 09 '14 at 08:19

1

well, when you execute ' '*a in python you are actually doing a hidden for loop

answered Jun 09 '14 at 08:19

Yuri

351
1
5

Can we say that Mathematically the time complexity of the code in python is better than that of C?

3 Answers3